我的 exp 用的是循环写法,写出来长这样:
void exp(int f[], int n) {
static int a[MAX_NTT], b[MAX_NTT];
int m = a[0] = 1;
while (m < (n << 1)) {
ln(a, b, m);
for (int i = 0; i < m; i++) {
b[i] = f[i] + !i - b[i];
if (b[i] >= P) b[i] -= P;
if (b[i] < 0) b[i] += P;
}
m <<= 1;
ntt(a, m, 1); ntt(b, m, 1);
for (int i = 0; i < m; i++)
a[i] = 1ll * a[i] * b[i] % P;
ntt(a, m, -1);
for (int i = m; i < (m << 1); i++)
a[i] = b[i] = 0;
}
for (int i = 0; i < n; i++) f[i] = a[i];
for (int i = 0; i < (n << 2); i++) a[i] = b[i] = 0;
}
然后我传进去的这个 n
,是最小的不小于原题给出的 N 的 2 的幂次。
然后我发现最大的一层 while
循环无论条件写成 m < (n << 1)
还是 m <= (n << 1)
都可以过。所以写小于号本来就是对的还是单纯数据没卡?