一个问题
查看原帖
一个问题
124683
Krystallos楼主2021/1/16 11:34

我的 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 ,是最小的不小于原题给出的 NN22 的幂次。 然后我发现最大的一层 while 循环无论条件写成 m < (n << 1) 还是 m <= (n << 1) 都可以过。所以写小于号本来就是对的还是单纯数据没卡?

2021/1/16 11:34
加载中...