多项式的基本概念 多项式的度 多项式的乘法 多项式的逆元 若存在 g(x)g(x)g(x) 满足： f(x)g(x)≡1(modxn)f(x)g(x) \equiv 1 \pmod{x^n} f(x)g(x)≡1(modxn) 则称 g(x)g(x)g(x) 为 f(x)f(x)f(x) 在模 xnx^nxn 意义下的逆元，g(x)=f−1(x)g(x)=f^{-1}(x)g(x)=...

NTT 有时候，题目要求对一个大质数（特别是998244353之类的数）取模，就不能用FFT，而是用NTT。 NTT采用原根替代单位根，如果不了解原根，请参考这篇博客。 常见NTT质数表： a×2b+1a\times 2^b+1a×2b+1 a b g 3 1 1 2 5 1 2 2 17 1 4 3 97 3 5 5 193 3 6 5 257 1 8 ...