求助,NTT写的过不去
查看原帖
求助,NTT写的过不去
115003
te5555楼主2020/5/8 21:35

RT,这是我的NTT

 for (register int i = 1; i < lim; i <<= 1)
    {
        int p = i << 1;
        int tG = qpow(op ? G : invG, (mod - 1) / p, mod);
        for (register int k = 0; k < lim; k += p)
        {
            int buf = 1;
            for (register int l = k; l < k + i; l++)
            {
                int tt = buf * f[i + l] % mod;
                f[i + l] = (mod+f[l] - tt) % mod;
                f[l] = (f[l] + tt) % mod;
                buf = buf * tG % mod;
            }
        }
    }

这是题解的

for (int i = 1; i < lim; i <<= 1) {
		int rot = qpow(op == 1 ? G : invG, (mod - 1) / (i << 1), mod);
		for (int j = 0; j < lim; j += (i << 1)) {
			int w = 1;
			for (int k = 0; k < i; k++, w = 1ll * w * rot % mod) {
				int x = f[j + k], y = 1ll * w * f[i + k + j] % mod;
				f[j + k] = (x + y) % mod, f[i + j + k] = (x - y + mod) % mod;
			}
		}
	}

把我这个换成题解的就过得去

但是我觉得这两种写法没什么不同呀

求大佬赐教

2020/5/8 21:35
加载中...