多項式板子
多項式板子
我是面向過程愛好者。
有時間大概會改 DFT 的實現，現在的速度還行。
f != g 表示 f 和 g 不是同一個數組，未加說明 \(f, g\) 都是多項式。
函數（都可以在 ExP:: 中找到）：
int Up(n)：返回 \(\ge n\) 的第一個 \(2\) 的次冪。
void Dft(f, l = 2^k)：對長為 \(l\) 的 \(f\) 做 DFT，更改原數組。
void Idf(f, l = 2^k)：對長為 \(l\) 的 對 \(f\) 做 IDFT，更改原數組。
void Add(f, g, l = 2^k)：對長為 \(l\) 的 \(f,g\) 做和卷積，放到 \(f\) 里，不更改 \(g\) 的值。
void Sub(f, g, l = 2^k)：對長為 \(l\) 的 對 \(f,g\) 做差卷積，放到 \(f\) 里，不更改 \(g\) 的值。
void Inv(f, g != f, l = 2^k)：對長為 \(l\) 的 \(f\) 求逆，放到 \(g\) 里。
void Sqrt(f, g != f, l = 2^k)：對長為 \(l\) 的 \(f\) 開根，需滿足 \(f_0 = 1\)，放到 \(g\) 里。
void Div(f, g != f, h != g, l = 2^k)：對長為 \(l\) 的 \(f,g\) 求 \(\frac fg\)，放到 \(g\) 里，快于求逆后卷積。
void Ln(f, g != f, l = 2^k)：對長為 \(l\) 的 \(f\) 求 \(\ln\)，需滿足 \(f_0 = 1\)，放到 \(g\) 里。
void Exp(f, g != f, l = 2^k)：對長為 \(l\) 的 \(f\) 求 \(\exp\)，需滿足 \(f_0 = 0\)，放到 \(g\) 里。
void Der(f, g, l = 2^k)：對長為 \(l\) 的 \(f\) 求導，放到 \(g\) 里。
void Int(f, g, l = 2^k)：對長為 \(l\) 的 \(f\) 積分，放到 \(g\) 里。
int Bt(f, g, l = 2^x, k)：對長為 \(l\) 的 \(f,g\) 求 \([x^k]\frac fg\)。
還有一點優化時的函數，沒啥用。
int Dbl(f, l = 2^k)：對長為 \(l\) 的點值 \(f\)，用更快的速度（兩次長為 \(n\) 的 FFT）求出長為 \(2n\) 的點值。
int Dinv(f, g, h, l = 2^k)：對長為 \(l\) 的 \(f\) 和 點值 \(g, h\)，其中 \(h = \hat{q}, f = \frac 1q \bmod {x ^ l}, g = \hat{f}\)，迭代出 \(f = \frac 1q \bmod {x ^ {2l}}\)，會更改 \(h\)，不會更改 \(g\)。
能過板子題，不保證沒問題。
Code
int Fpw(int a, int b){
int ans = 1;
for(; b; a = 1ll * a * a % MOD, b >>= 1) if(b & 1) ans = 1ll * ans * a % MOD;
return ans;
}
namespace OpP{
int Wn[N << 1], inv[N];
int Up(int n){ return pow(2, ceil(log(n) / log(2))); }
struct INIT{ INIT(){
int n = 1 << __lg(N), *p = Wn; *p = 1;
for(int i = 1; i < n; i <<= 1){
int w = Fpw(G, (MOD - 1) / (i << 1)), v = 1;
for(int j = 0; j < i; ++j) *++p = v, v = 1ll * v * w % MOD;
}
inv[0] = 1; for(int i = 1; i <= n; ++i) inv[i] = 1ll * inv[i - 1] * i % MOD;
inv[n] = Fpw(inv[n], MOD - 2);
for(int i = n; i; --i) inv[i - 1] = 1ll * exchange(inv[i], 1ll * inv[i] * inv[i - 1] % MOD) * i % MOD;
} } Initer;
void Dft(int *f, int l){
for(int i = 0, j = 0; i < l; ++i){
if(i < j) swap(f[i], f[j]);
for(int k = l >> 1; (j ^= k) < k; k >>= 1) ;
}
for(int k = 1; k < l; k <<= 1)
for(int i = 0; i < l; i += k << 1)
for(int j = 0, *p = Wn + k; j < k; ++j, ++p){
llt a = f[i + j], b = 1ll * (*p) * f[i + j + k];
f[i + j] = (a + b) % MOD, f[i + j + k] = (a - b) % MOD;
}
}
void Idf(int *f, int l){
Dft(f, l), reverse(&f[0] + 1, &f[0] + l);
for(int i = 0, v = inv[l]; i < l; ++i) f[i] = 1ll * f[i] * v % MOD;
}
}
namespace ExP{
using namespace OpP;
#define fk (k >> 1)
#define Set(a, l) memset(a, 0, sizeof(*a) * (l))
#define Cpy(a, b, l) memcpy(a, b, sizeof(*a) * (l))
void Dbl(int *f, int l){
int a[N]; Cpy(a, f, l);
Idf(f, l);
for(int i = 0, *p = Wn + l; i < l; ++i, ++p) f[i] = 1ll * f[i] * (*p) % MOD;
Dft(f, l);
for(int i = l << 1; ~i; --i) f[i] = i & 1 ? f[i >> 1] : a[i >> 1];
}
void Add(int *f, int *g, int l){
int t[N]; Cpy(t, g, l);
Dft(f, l), Dft(t, l);
for(int i = 0; i < l; ++i) f[i] = 1ll * f[i] * t[i] % MOD;
Idf(f, l);
}
void Sub(int *f, int *g, int l){
int t[N]; Cpy(t, g, l);
Idf(f, l), Dft(t, l);
for(int i = 0; i < l; ++i) f[i] = 1ll * f[i] * t[i] % MOD;
Dft(f, l);
}
void Dinv(int *f, int *g, int *h, int l){
for(int i = 0; i < l; ++i) h[i] = 1ll * h[i] * g[i] % MOD;
Idf(h, l), Set(h, l >> 1), Dft(h, l);
for(int i = 0; i < l; ++i) h[i] = 1ll * h[i] * g[i] % MOD;
Idf(h, l);
for(int i = l >> 1; i < l; ++i) f[i] = -h[i];
}
void Inv(int *f, int *g, int l){
int ta[N], tb[N];
Set(ta, l), Set(tb, l), Set(g, l);
g[0] = Fpw(f[0], MOD - 2);
for(int k = 2; k <= l; k <<= 1){
Cpy(ta, f, k), Cpy(tb, g, k);
Dft(ta, k), Dft(tb, k), Dinv(g, tb, ta, k);
}
}
void Sqrt(int *f, int *g, int l){
int ta[N], tb[N], tc[N], th[N];
Set(ta, l), Set(tb, l), Set(tc, l), Set(th, l), Set(g, l);
assert(f[0] == 1 || f[0] == 1 - MOD), ta[0] = g[0] = 1, th[0] = 1; int i2 = (MOD + 1) >> 1;
for(int k = 2; k <= l; k <<= 1){
for(int i = 0; i < fk; ++i) ta[i] = 1ll * ta[i] * ta[i] % MOD;
Idf(ta, fk);
for(int i = 0; i < fk; ++i) ta[i + fk] = (ta[i] - f[i]) % MOD, ta[i] = 0;
for(int i = fk; i < k; ++i) ta[i] = (ta[i] - f[i]) % MOD;
Dft(ta, k), Cpy(tb, th, k), Dft(tb, k);
for(int i = 0; i < k; ++i) ta[i] = 1ll * ta[i] * tb[i] % MOD;
Idf(ta, k);
for(int i = fk; i < k; ++i) g[i] = -1ll * ta[i] * i2 % MOD;
if(k != l) Cpy(ta, g, k), Dft(ta, k), Cpy(tc, ta, k), Dinv(th, tb, tc, k);
}
}
void Div(int *f, int *g, int *h, int l){
int ta[N], tb[N], tc[N], th[N];
Set(ta, l), Set(tb, l), Set(tc, l), Set(th, l), Set(h, l);
th[0] = Fpw(g[0], MOD - 2), h[0] = 1ll * th[0] * f[0] % MOD;
for(int k = 2; k <= l; k <<= 1){
Cpy(tb, g, k), Dft(tb, k), Cpy(ta, h, k), Dft(ta, k);
for(int i = 0; i < k; ++i) ta[i] = 1ll * ta[i] * tb[i] % MOD;
Idf(ta, k), Set(ta, fk);
for(int i = fk; i < k; ++i) ta[i] = (ta[i] - f[i]) % MOD;
Dft(ta, k), Cpy(tc, th, k), Dft(tc, k);
for(int i = 0; i < k; ++i) ta[i] = 1ll * ta[i] * tc[i] % MOD;
Idf(ta, k);
for(int i = fk; i < k; ++i) h[i] = -ta[i];
if(k != l) Dinv(th, tc, tb, k);
}
}
inline void Der(int *f, int *g, int l){
for(int i = 1; i < l; ++i) g[i - 1] = 1ll * f[i] * i % MOD;
g[l - 1] = 0;
}
inline void Int(int *f, int *g, int l){
for(int i = l - 1; i; --i) g[i] = 1ll * f[i - 1] * inv[i] % MOD;
g[0] = 0;
}
void Ln(int *f, int *g, int l){
assert(f[0] == 1 || f[0] == 1 - MOD); int t[N];
Der(f, g, l), Div(g, f, t, l), Int(t, g, l);
}
void Exp(int *f, int *g, int l){
int ta[N], tb[N], tc[N], td[N], th[N]; assert(f[0] == 0);
Set(ta, l), Set(tb, l), Set(tc, l), Set(td, l), Set(g, l), tc[0] = g[0] = 1, th[0] = 1;
for(int k = 2; k <= l; k <<= 1){
Cpy(tb, th, fk), Dft(tb, fk);
for(int i = 0; i < fk; ++i) td[i] = (1ll * tb[i] * tc[i] - 1) % MOD;
Dbl(td, fk);
for(int i = 0, *p = Wn + fk, t; t = 1ll * i * fk % k, i < k; ++i)
td[i] = 1ll * td[i] * (t < fk ? p[t] : -p[t - fk]) % MOD;
Der(f, tc, fk), Dft(tc, k);
for(int i = 0; i < k; ++i) td[i] = 1ll * td[i] * tc[i] % MOD;
Idf(td, k), Der(g, ta, fk), Dft(ta, fk);
for(int i = 0; i < fk; ++i) ta[i] = 1ll * ta[i] * tb[i] % MOD;
Idf(ta, fk), Der(f, tc, k);
for(int i = 0; i < fk - 1; ++i) ta[i + fk] = (1ll * ta[i + fk] + ta[i] - tc[i]) % MOD, ta[i] = 0;
for(int i = fk - 1; i < k - 1; ++i) ta[i] = (ta[i] - tc[i]) % MOD;
for(int i = fk; i < k - 1; ++i) ta[i] = (ta[i] - td[i]) % MOD;
Int(ta, ta, k), Add(ta, g, k);
for(int i = fk; i < k; ++i) g[i] = -ta[i];
if(k != l) Cpy(ta, g, k), Dft(ta, k), Cpy(tc, ta, k), Cpy(tb, th, k), Dft(tb, k), Dinv(th, tb, ta, k);
}
}
int Bt(int *cf, int *cg, int l, int k){
int f[N], g[N], i2 = (MOD + 1) >> 1;
Cpy(f, cf, l), Cpy(g, cg, l), Dft(f, l), Dft(g, l);
for(; k; k >>= 1){
Dbl(f, l), Dbl(g, l);
if(k & 1){
for(int i = 0; i < l; ++i)
f[i] = (1ll * f[i] * g[i ^ l] - 1ll * f[i ^ l] * g[i]) % MOD * i2 % MOD;
for(int i = l - 1, *p = Wn + l + 1; i; --i, ++p)
f[i] = 1ll * f[i] * (-*p) % MOD;
}else for(int i = 0; i < l; ++i)
f[i] = (1ll * f[i] * g[i ^ l] + 1ll * f[i ^ l] * g[i]) % MOD * i2 % MOD;
for(int i = 0; i < l; ++i) g[i] = 1ll * g[i] * g[i ^ l] % MOD;
}
Idf(f, l), Idf(g, l);
return 1ll * f[0] * Fpw(g[0], MOD - 2) % MOD;
}
#undef fk
#undef Set
#undef Cpy
}
本文來自博客園，作者：xrlong，轉載請注明原文鏈接：http://www.rzrgm.cn/xrlong/p/18928765
版權聲明：本作品采用 「署名-非商業性使用-相同方式共享 4.0 國際」許可協議（CC BY-NC-SA 4.0） 進行許可。
浙公網安備 33010602011771號