模板 - 数学 - 快速傅里叶变换/快速数论变换(FFT/NTT)

先看看。

通常模数常见的有998244353,1004535809,469762049,这几个的原根都是3。
所求的项数还不能超过2的23次方(因为998244353的分解)。

感觉没啥用。

#include <cstdio>
#include <cstring> template <class T>
inline void swap(T &a, T &b)
{
T c;
c = a;
a = b;
b = c;
} const int siz = ; const int P = , G = ; inline int pow(int a, int b)
{
int r = ; while (b)
{
if (b & )
r = 1LL * r * a % P; b >>= , a = 1LL * a * a % P;
} return r;
} inline void calculateNTT(int *s, int n, int f)
{
{
int cnt = ; static int rev[siz]; while (n >> cnt)++cnt; --cnt; memset(rev, , sizeof rev); for (int i = ; i < n; ++i)
{
rev[i] |= rev[i >> ] >> ;
rev[i] |= (i & ) << (cnt - );
} for (int i = ; i < n; ++i)if (i < rev[i])swap(s[i], s[rev[i]]);
} {
for (int i = ; i < n; i <<= )
{
int wn = pow(G, (P - ) / (i * )); if (f == -)wn = pow(wn, P - ); for (int j = ; j < n; j += (i << ))
{
int wk = ; for (int k = ; k < i; ++k, wk = 1LL * wk * wn % P)
{
int x = s[j + k];
int y = 1LL * s[i + j + k] * wk % P; s[j + k] = x + y;
s[i + j + k] = x - y; s[j + k] = (s[j + k] % P + P) % P;
s[i + j + k] = (s[i + j + k] % P + P) % P;
}
}
}
} {
if (f == -)
{
int inv = pow(n, P - ); for (int i = ; i < n; ++i)
s[i] = 1LL * s[i] * inv % P;
}
}
} signed main(void)
{
static char sa[siz];
static char sb[siz]; scanf("%s", sa);
scanf("%s", sb); static int la, a[siz];
static int lb, b[siz]; la = strlen(sa);
lb = strlen(sb); for (int i = ; i < la; ++i)a[i] = sa[la - i - ] - '';
for (int i = ; i < lb; ++i)b[i] = sb[lb - i - ] - ''; int len; for (len = ; len < la || len < lb; len <<= ); calculateNTT(a, len << , +);
calculateNTT(b, len << , +); for (int i = ; i < len << ; ++i)a[i] = 1LL * a[i] * b[i] % P; calculateNTT(a, len << , -); for (int i = ; i < len << ; ++i)a[i + ] += a[i] / , a[i] = a[i] % ; len <<= ; while (!a[len])--len; for (int i = len; ~i; --i)printf("%d", a[i]); puts("");
}

快速傅里叶变换FFT

上一篇:快速傅里叶变换(FFT)相关内容汇总


下一篇:「算法笔记」快速数论变换(NTT)