User:DQ9911
多项式全家桶
[edit]快速傅立叶变换
[edit]定义单位根: <br>DFT: <br>IDFT:
一个特殊的技巧:
设.
则有
使用这个技巧可以将3次dft优化到2次dft, 但有精度问题,一定要预处理单位根
typedef double db;
typedef complex<db> cpd;
/* 约提速两倍
* struct cpd {
* db x, y;
* cpd(db _x=0,db _y=0){x=_x,y=_y;}
* cpd &operator += (const cpd&rhs){return *this={x+rhs.x,y+rhs.y};}
* cpd &operator -= (const cpd&rhs){return *this={x-rhs.x,y-rhs.y};}
* cpd &operator *= (const cpd&rhs){return *this={x*rhs.x-y*rhs.y,x*rhs.y+y*rhs.x};}
* cpd &operator /= (const db&rhs){return *this={x/rhs,y/rhs};}
* cpd operator + (const cpd&rhs){cpd ret=*this;return ret+=rhs;}
* cpd operator - (const cpd&rhs){cpd ret=*this;return ret-=rhs;}
* cpd operator * (const cpd&rhs){cpd ret=*this;return ret*=rhs;}
* cpd operator / (const db&rhs){cpd ret=*this;return ret/=rhs;}
* friend cpd exp(const cpd&rhs){return cpd(cos(rhs.y),sin(rhs.y))*exp(rhs.x);}
* friend cpd conj(const cpd&rhs){return cpd(rhs.x, -rhs.y);}
* db real(){return x;}
* db imag(){return y;}
* };
*/
const double pi = acos(-1.0);
const int N = 1 << 18 | 7;
const int L = 19; // lg(n) + 1
vector<cpd> w[2][L];
void fft_init() {
for(int i = 1; i < L; i++) {
w[0][i].resize(1 << i), w[1][i].resize(1 << i);
for(int j = 0; j < 1 << i; j++) {
w[0][i][j] = exp(cpd(0, j * 2 * pi / (1 << i)));
w[1][i][j] = conj(w[0][i][j]);
}
}
}
void fft(cpd *y, int len, int on) { // on == 0: dfn, on == 1 : idft
static int r[N], i, j, k, l, nl;
static cpd u, v;
l = __builtin_ctz(len);
if(l != nl) for(i = 0, nl = l; i < len; i++)
r[i] = (r[i>>1]>>1)|((i&1)<<l-1);
for(i = 0; i < len; i++)
if(i<r[i]) swap(y[i],y[r[i]]);
for(i = 1, l = 1; i < len; i<<=1, l++)
for(j = 0; j < len; j += i<<1)
for(k = j; k < j + i; k++)
u=y[k], v=y[k+i]*w[on][l][k-j],
y[k]=u+v, y[k+i]=u-v;
if(on) for(i=0;i<len;i++) y[i]/=len;
}
任意模数FFT
[edit]先拆系数,直接暴力卷积是7次dft
只需要求、、、四个卷积
优化方法:
设 、
使用上面提到共轭复数的技巧,可将dft次数优化到4次
const int M = (1<<15)-1;
const int mod = 1e6 + 3;
void conv(int *a, int *b, int *c, int l1, int l2) {
static cpd dft[4], x[4][N*2];
static int i, j, d[4];
int len = l1 + l2 - 1;
while(len & (len - 1)) len += len & -len;
for(i = 0; i < len; i++) {
x[0][i] = i<l1? cpd(a[i] & M, a[i] >> 15):0;
x[1][i] = i<l2? cpd(b[i] & M, b[i] >> 15):0;
}
fft(x[0], len, 0), fft(x[1], len, 0);
const cpd half = cpd(0.5, 0);
for(i = j = 0; i < len; i++, j = len - i) {
dft[0] = x[0][i] * x[1][i] * half;
dft[1] = conj(x[0][j]) * x[1][i] * half;
dft[2] = x[0][i] * conj(x[1][j]) * half;
dft[3] = conj(x[0][j]) * conj(x[1][j]) * half;
x[2][i] = dft[0] + dft[1];
x[3][i] = dft[2] - dft[3];
}
fft(x[2], len, 1), fft(x[3], len, 1);
for(i = 0; i < len; i++) {
d[0] = ll(x[2][i].x + 0.5) % mod;
d[1] = ll(x[2][i].y + 0.5) % mod;
d[2] = ll(x[3][i].y + 0.5) % mod;
d[3] = ll(x[3][i].x + 0.5) % mod;
c[i] = ((1ll<<30) * d[3] % mod + d[0]) % mod;
c[i] = (c[i] + (1ll<<15) * (d[1] + d[2])) % mod;
}
}
快速数论变换
[edit]G为模P意义下的一个原根,此时用来代替
常用NTT模数及其原根:,不能超过
NTT的卷积结果为循环卷积, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\textstyle c[i] = \displaystyle \sum_{(j+k)\equiv (mod \space n)} a[j] \times b[k]}
P r k G
104857601 25 22 3
167772161 5 25 3
469762049 7 26 3
998244353 119 23 3
1004535809 479 21 3
2013265921 15 27 31
2281701377 17 27 3
typedef long long ll;
const int N = 1 << 18 | 7;
const int P = 479 << 21 | 1;
inline int sub(int x, int y) {
return (x-=y)<0?x+P:x;
}
inline int add(int x, int y) {
return (x+=y)>=P?x-P:x;
}
template<int mod>
int power_mod(int a, int b) {
int ret = 1;
for(a %= mod; b; b>>=1,a=(ll)a*a%mod)
if(b&1) ret = (ll)ret*a%mod;
return ret;
}
template<int G, int P>
struct NTT {
NTT() { ntt_init();}
int w[19][2];
void ntt_init() {
for(int i = 1; i < 19; i++) {
w[i][0] = power_mod<P>(G, P-1>>i);
w[i][1] = power_mod<P>(w[i][0], P-2);
}
}
void ntt(int *y, int len, int on) {
static int r[N], nl, ww, wn, u, v;
int i, j, k, l = __builtin_ctz(len) - 1;
if(nl != len) {
for(i = 0, nl = len; i < len; i++)
r[i] = (r[i>>1]>>1)|(i&1)<<l;
}
for(i = 0; i < len; i++)
if(i < r[i]) swap(y[i], y[r[i]]);
for(i = 1, l = 1; i < len; i <<= 1, l++)
for(j = 0, wn = w[l][on]; j < len; j+=i<<1)
for(k = j, ww = 1; k < j + i; k++, ww = (ll)ww*wn%P)
u = y[k], v = (ll)y[k+i]*ww%P,
y[k] = add(u,v), y[k+i] = sub(u,v);
if(on) {
int invl = power_mod<P>(len, P - 2);
for(i = 0; i < len; i++) y[i] = (ll)y[i]*invl%P;
}
}
};
NTT<3, P> ntt;
多项式求逆
[edit]Failed to parse (unknown function "\space"): {\textstyle A(x)B(x) = 1 (mod \space x^n)}
设Failed to parse (unknown function "\space"): {\textstyle A(x)B_0(x) = 1 (mod \space x^n), A(x)B(x) = 1 (mod \space x^{2n})}
则有Failed to parse (unknown function "\space"): {\textstyle A(x)(B(x) - B_0(x)) = 0 (mod \space x^n)} ,平方得到Failed to parse (unknown function "\space"): {\textstyle B^2(x) - 2B_0(x)B(x) + B_0^2(x) = 0 (mod \space x^{2n})}
两边同时乘, Failed to parse (unknown function "\space"): {\textstyle B(x) = B_0(x)(2 - A(x)B_0(x)) (mod \space x^{2n})} , 使用牛顿迭代法复杂度为
void invpoly(int *A, int *B, int len) {
static int x[N], i;
if(len == 1) return B[0] = 1, void(B[1] = 0);
invpoly(A, B, len>>1);
for(i = 0; i < len; i++) x[i] = A[i], x[i+len]=B[i+len]=0;
ntt.ntt(x, len<<1, 0), ntt.ntt(B, len<<1, 0);
for(i = 0; i < 2 * len; i++)
B[i] = B[i] * (2 + (ll)(P-B[i])*x[i]%P)%P;
ntt.ntt(B, len<<1, 1);
for(i = len; i < 2 * len; i++) B[i] = 0;
}
多项式取ln
[edit]设,两边求导,求的逆元即可, 复杂度
void logpoly(int *A, int *B, int len) {
static int x[N], i;
invpoly(A, x, len);
for(i = 0; i < len; i++) B[i] = A[i+1]*(i+1ll)%P;
for(i = len-1; i < 2 * len; i++) B[i] = 0;
ntt.ntt(x, len<<1, 0), ntt.ntt(B, len<<1, 0);
for(i = 0; i < 2 * len; i++)
B[i] = (ll)x[i]*B[i]%P;
ntt.ntt(B, len<<1, 1);
for(i = len; i < 2 * len; i++) B[i] = 0;
for(i = len-1; i; i--) B[i] = (ll)B[i-1]*inv[i]%P;
B[0] = 0;
}
多项式exp
[edit]cdq分治求法:
设, 则
设, .
则有
下面做法: 设,
利用在出的泰勒展开式得出模与模时的递推式,再牛顿迭代.
复杂度: (常数堪比慎用)
void exppoly(int *A, int *B, int len) {
static int x[N], i;
if(len == 1) return B[0] = 1, void(B[1] = 0);
exppoly(A, B, len>>1);
logpoly(B, x, len); x[0] = sub(x[0], 1);
for(i = 0; i < len; i++) x[i] = sub(A[i], x[i]);
for(i = len; i < 2 * len; i++) x[i] = 0;
ntt.ntt(B, len<<1, 0), ntt.ntt(x, len<<1, 0);
for(i = 0; i < 2 * len; i++)
B[i] = (ll)B[i] * x[i] % P;
ntt.ntt(B, len<<1, 1);
for(i = len; i < 2 * len; i++) B[i] = 0;
}
多项式求幂
[edit]
先求, 再求即可. 细节略.
多项式除法
[edit],设A, B, C, D分别为Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\textstyle n、m, n - m, m - 1} 阶多项式
即
在模意义下计算逆元即可
可持久化字典树
[edit]用于求解异或最大值问题
通过记录每个节点插入次数实现可持久化
struct Trie {
int cnt[N * 31], c[N * 31][2], tot;
void init() {
tot = 0;
c[0][0]=c[0][1]=0;
}
int newnode() {
tot++;
c[tot][0] = c[tot][1] = 0;
return tot;
}
void insert(int last, int &now, int x) {
/* last表示上个版本的根节点,now表示修改后版本的根节点 */
int tmp = now = newnode();
for(int i = 29; ~i; i--) {
int k = x>>i&1;
c[tmp][k] = newnode(), c[tmp][k^1] = c[last][k^1];
tmp = c[tmp][k], last = c[last][k];
cnt[tmp] = cnt[last] + 1;
}
}
int query(int l, int r, int x) { //查询区间异或最大值
for(int i = 29; ~i; i--) {
int k = ~x>>i&1;
if(cnt[c[r][k]] > cnt[c[l][k]])
x ^= k << i, r = c[r][k], l = c[l][k];
else x ^= (k^1)<<i, r = c[r][k^1], l = c[l][k^1];
}
return x;
}
} per_trie;
拉格朗日插值
[edit]给一个阶多项式的个点,且
现给一个的值,要求计算的值。
构造多项式如下
只需预处理, 求值即可.
void Lagrange(int *x, int *y, int *a, int n) {
for(int i = 0; i <= n; i++) {
a[i] = 1;
for(int j = 0; j <= n; j++)
if(j != i) a[i]=(ll)a[i]*(x[i]-x[j]+mod)%mod;
a[i] = (ll)power_mod(a[i], mod-2)*y[i]%mod;
}
}
int calc(int *a, int *x, int *y, int n, int v) {
static int t1[N], invi[N]; // invi[i]:inv(v-x[i])
for(int i=0; i<=n; i++)
if(v==x[i]) return y[i];
/* 这段可以不写下面直接求逆元,复杂度多个lg,实际影响不大
t1[0] = (v-x[0]+mod)%mod;
for(int i = 1; i <= n; i++)
t1[i] = (ll)t1[i-1]*(v-x[i]+mod)%mod;
invi[n] = power_mod(t1[n], mod-2);
for(int i = n-1; ~i; i--)
invi[i] = (ll)invi[i+1]*(v-x[i+1]+mod)%mod;
for(int i = 1; i <= n; i++)
invi[i] = (ll)invi[i]*t1[i-1]%mod;
*/
int ret = 0;
for(int i = 0; i <= n; i++)
ret = (ret + (ll)t1[n]*invi[i]%mod*a[i])%mod;
return ret;
}