「OI之路」03数学-14多项式全家桶

多项式全家桶
板子并不全,对测速、其他板子感兴趣的请看这里

upd:好像这个更全啊,各种能写的黑科技都写了

一些约定

多项式的度:最高项次数;

多项式的次数界:任何一个严格大于多项式次数的数

FFT

前置知识:

  1. 复数,由实数和虚数(单位为i)组成
  2. 欧拉公式 $e^{xi}=cos(x)+sin(x) i$
  3. 单位复数根 $\omega_n^k = e^{ 2 \pi \frac{k}{n} }$ ,可见 $(\omega_n^k)^2=(\omega_n^{k+n/2})^2$

解决的主要问题:多项式乘法
设最高次项为n,则暴力为 $O(n^2)$
在系数为实数域下,借助单位复数根的性质优化复杂度为nlogn

思路:
将多项式看作函数
从函数的系数表达法 求值 为点值表达法,最高次为n的函数,至少(倍数点的存在)需要n+1个点确定
点值表达法的两个函数相乘,时间为n(相同x,x不变,y相乘)
从点值表达法 插值 为系数表达法(降低为nlogn)

分治:
对于 $T(x)=\sum a_i x^i$
将其奇偶分离,$T(x)=A(x^2)+x \times B(x^2)$
其中A为偶数,多项式长度减半,但变成两个
然后因为平方相同,联想到单位根的性质,不妨将其作为x来代入
所以对于当前需要带入的n个,只要带入前面n/2个即可(n都是指大于多项式次数的2的次幂)
那么根据主定理可知其复杂度为 $nlogn$ ,如果不太懂可结合code
然后插值的话,结论是将单位 $\omega_n^1变为 \omega_n^{-1}$ ,然后退出时将结果除以n
证明见下面DFT

实现:
递归版因其空间开销即常数巨大,很少使用
如果每次都是将奇数位(次幂为偶数)放在前面,则最后奇偶分离的结果下, $num[i]=a[二进制翻转(i)]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
namespace PP
{
const int LN=1<<21;int bin[30];
const double PI=acos(-1);
struct Cp
{
double a,b;Cp(double x=0,double y=0){a=x,b=y;}
Cp operator + (const Cp &t)const{return Cp(a+t.a,b+t.b);}
Cp operator - (const Cp &t)const{return Cp(a-t.a,b-t.b);}
Cp operator * (const Cp &t)const{return Cp(a*t.a-b*t.b,b*t.a+a*t.b);}
Cp operator * (const double &t)const{return Cp(a*t,b*t);}
Cp operator ~ ()const{return Cp(a,-b);}
};
struct NTT
{
int R[LN];Cp w[LN];
NTT(){
bin[0]=1;for(int i=1;i<30;i++) bin[i]=bin[i-1]<<1;
for(int i=0;i<LN;i++) w[i]=Cp(cos(2*PI/LN*i),sin(2*PI/LN*i));
}
void DFT(Cp A[],int lg,int op=0)
{
int m=bin[lg];if(op) reverse(A+1,A+m);
for(int i=1;i<m;i++){R[i]=(R[i>>1]>>1)|((i&1)<<(lg-1));if(i<R[i])swap(A[i],A[R[i]]);}
for(int ln=1;ln<m;ln<<=1) for(int st=0;st<m;st+=ln<<1) for(int k=0;k<ln;k++)
{
Cp t=w[LN/(ln<<1)*k]*A[st+ln+k];
A[st+ln+k]=A[st+k]-t;A[st+k]=A[st+k]+t;
}
}
}ntt;
};

NTT

超赞的教程
笔记:
当p为素数,存在其原根g,使得 $g^0,g^1,… g^{p-2}$ 互不相同
然后因为我们需要分治,同样希望能按2分解,
所以p的形式必须为 $t \times 2^k+1$ ,然后能处理 $n \leq 2^k$ 的数据
设 $g_n=g^{(p-1)/n}$
然后通过各种方式可证明其满足我们用到的单位复数根的各种性质
超详细原根表原根表2号
最常见:998244353、1004535809,原根为3

卷积的应用

  1. 带通配符字符串匹配问题(具体位置);很容易想到把字符串翻转后用卷积表示以某个位置后开始匹配的情况

    1)如果是比较基础的是保证字符集大小,那么枚举每种字符,数匹配数即可,例题:bzoj4503两个串

    2)字符集不保证其实也能做,考虑怎么把a和b独立开来;如果统计$[a=b]$的话,好像不是很行,但我们只需要知道是否不存在$[a \ne b]$,那么如果是’?’的话设为0就好了,不妨考虑欧几里得距离的平方=$(a-b)^2=a^2+b^2-2ab$,这个预处理区间平方和就好了,例题:bzoj4259 残缺的字符串

    3)差不多的:bzoj3160 万径人踪灭code,要求不连续所以要多写个manacher

  2. 解决若干个多项式的乘积的时候,像哈夫曼树那样搞个堆维护多项式可以达到速度下界,就像合并果子(以前都是用分治fft的)

常数优化

还是推荐看毛啸的论文,非常多卡常技巧

  1. fft有个利用复数的trick,将3次减少到2次:$C=A*B,构造D_i=(a_i+b_i)+(a_i-b_i)i,C_i=\frac{1}{4}real(D^2 [x^i])$
  2. 预处理单位根,fft提精度ntt提速度
  3. 我一般写IDFT都会这样写

拆系数FFT

暂时只会7次的,就是设 $m0=\sqrt M$ ,然后带余除法一下,展开成4个多项式
DFT后,合并起来,然后外面系数相同的有3种,IDFT共3次,然后再把系数还原
samjia的

4次的板子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for(int i=0;i<=n;i++) {int t=qread();A[i]=Cp(t>>16,t&(MOD-1));}
for(int i=0;i<=m;i++) {int t=qread();B[i]=Cp(t>>16,t&(MOD-1));}
ntt.DFT(A,lg);ntt.DFT(B,lg);
for(int i=0;i<M;i++)
{
int id=i?M-i:0;
Cp f0=(A[i]-(~A[id]))*Cp(0,-0.5),f1=(A[i]+(~A[id]))*0.5;
Cp g0=(B[i]-(~B[id]))*Cp(0,-0.5),g1=(B[i]+(~B[id]))*0.5;
C[i]=f1*g1;D[i]=f1*g0+f0*g1+f0*g0*Cp(0,1);
}
ntt.DFT(C,lg,1);ntt.DFT(D,lg,1);double fk=1.0/M;
for(int i=0;i<=n+m;i++)
{
ll a=(ll)(C[i].a*fk+0.5)%p<<32;
ll b=(ll)(D[i].a*fk+0.5)%p<<16;
ll c=(ll)(D[i].b*fk+0.5)%p;
write1(((a+b+c)%p+p)%p);
}

分治FFT

常数优化:考虑到是循环卷积,长度并不需要倍长到$(r-l)+(mid-l)+1$,而是到$r-l+1$就行了,因为我们只需要后面的$r-mid$部分,而对一个$up(r-l+1)$做循环卷积并不会影响到(因为哪怕up没区别,都不会影响到,而现在循环长度更长)

例子:「CF553E」Kyoya and Train

有的时候你会发现要自己卷自己,例如uoj50「UR #3」链式反应,考虑每次用$[l,mid]更新[mid+1,r]$,那么我们在处理更新长度部分($i \in[1,r-l]$)讨论一下i,$当i \le l,只会被统计一次,系数=2;当i \le mid,会被统计两次,系数=1;否则系数=0$

DFT

补充一下这个,因为有些时候是不能分治的,需要求自动的循环卷积
(之所以这么说,是因为通常可以手动循环卷积,不过例如在快速幂里面就会多个log和大常数)
首先DFT是个循环卷积,只不过因为通常情况下,我们的n都是到2的次幂,是个线性卷积
有个性质(应用于复数根和原根,称之为单位根反演): $\frac{1}{k} \sum_{i=0}^{k-1} g_k^{ni}=[n\%k=0]$

把式子的简化版放在这里,完整版还是看myy的吧
$$
\begin{aligned}
C_r=& \sum [(p+q) \% n=r] a_pb_q\\
=& \frac{1}{n} \sum_{k=0}^{n-1} (w_n^{-r})^k \times (\sum (w_n^k)^p a_p ) \times (\sum (w_n^k)^q b_q )\\
&所以我们就能得到DFT和IDFT的式子\\
a_m&=\sum_{k=0}^{n-1} (w_n^m)^k b_k,
c_m=\frac{1}{n} \sum_{k=0}^{n-1} (w^{-m}_n)^k d_k\\
\end{aligned}
$$
于是就可以全自动了,复杂度n方,例题:CC的bike(毕克的题)

Bluestein’s Algorithm

自动循环卷积在条件允许的时候当然可以exp,复杂度nlogn但常数巨大;手动循环卷积的话复杂度是log方的

$$
\hat A_k=\sum_{i=0}^{n-1}A_i w_n^{ik},考虑怎么拆ik \\
myy论文上(疑似写错)的拆法是ik=\frac{i^2+k^2-(k-i)^2}{2},
\hat A_k=w_n^{k^2/2} \sum_{i=0}^{n-1}(A_i w_n^{i^2/2} )w_n^{(k-i)^2/2} \\
貌似还行,毕竟可以上下放大,但有没有可能mod恰好不是2n的倍数? \\
二次剩余当然不是我们希望的,还有i和k大小关系的问题,网上看到一个更好的拆法 \\
ik=C_{i+k}^2-C_{i}^2-C_{k}^2,
\hat A_k=w_n^{-C_{k}^2} \sum_{i=0}^{n-1}(A_i w_n^{-C_{i}^2} )w_n^{C_{i+k}^2} \\
IDFT也是类似,A_k=\frac{w_n^{C_{k}^2}}{n} \sum_{i=0}^{n-1}(\hat A_i w_n^{C_{i}^2} )w_n^{-C_{i+k}^2}
$$

牛顿迭代

牛顿迭代是全家桶的基础,请务必透彻理解

普通的牛顿迭代就是对方程求根(y=0),然后现在把x替换成一个多项式

然后模p是模长度,可以看作一个精度,然后我们迭代就是求想要的精度,后面的所有运算都是在这个意义下的
$$
设当前要处理的多项式组为 B_p表示模数为p,自定义函数f,求 f(B_p)=0(\%x^p) \\
对于f(B_p)在B_{\lceil p/2 \rceil}处泰勒展开,B_p-B_{\lceil p/2 \rceil}的前\lceil p/2 \rceil项都是0 \\
所以只需要展开前两项就能保证当前精度 \\
f(B_p)=0=f(B_{\lceil p/2 \rceil})+f’(B_{\lceil p/2 \rceil})(B_p-B_{\lceil p/2 \rceil})(\%x^p) \\
B_p=B_{\lceil p/2 \rceil}-\frac{f(B_{\lceil p/2 \rceil})}{f’(B_{\lceil p/2 \rceil})} (\%x^p) \\
请牢记,这里的f’是指 \frac{d}{db} f(b),跟多项式没啥关系,强烈建议做题感受
$$

然后以下介绍的东西都是log的,但常数不断增加

逆元(常数6)

首先$O(n^2)$的递推是常识:$[i=0]=\sum_{j=0}^i a_j*inv_{i-j}$,不难看出一个多项式存在逆元当且仅当其常数项存在逆元
$$
f(x)=A*x-1,f’(x)=A,B_p=B_{\lceil p/2 \rceil}-\frac{A*B_{\lceil p/2 \rceil}-1}{A} (\%x^p)=B_{\lceil p/2 \rceil}-(A*B_{\lceil p/2 \rceil}-1)*B_p (\%x^p) \\
然后观察可知括号内前半(上取整)都是0,可以将B_p替换成B_{\lceil p/2 \rceil},得
B_p=2B_{\lceil p/2 \rceil}-B^2_{\lceil p/2 \rceil}A (\%x^p)
$$

例题:bzoj3456

开方(常数18)

常数项如果没保证你可能需要一个二次剩余;如果懒的话可以看做多项式求幂用exp做

$f(x)=A-x^2=0,f’(x)=-2x,B_p=B_{\lceil p/2 \rceil}-\frac{A-B^2_{\lceil p/2 \rceil}}{-2B_{\lceil p/2 \rceil}}=\frac{B_{\lceil p/2 \rceil}^2+A}{2B_{\lceil p/2 \rceil}} (\%x^p)$

(带余)除法、取模(常数12)

定义: $\begin{equation} \label{div0} A(x) = D(x)B(x) + R(x) \end{equation}$
设A的度为n,B为m,则D为n-m,R不超过m-1

然后我们考虑一个骚操作,对于一个度为k的多项式T, $x^k T(\frac{1}{x})$ 等价于系数反转
$A^r(x)=D^r(x)B^r(x)+x^{n-m+1} R^r(x)$
注意到后面的部分不会影响到D,$D^r(x)=A^r(x) \times inv( B^r(x) ) (\mod x^{n-m+1})$

ln和exp(常数9、24)

可以看成是多项式丢到麦克劳森级数里面
$$
exp(A)=\sum A^i/i!,显然结果常数项=1 \\
ln(A)=-\sum_{i=1} \frac{(1-A)^i}{i},A常数项=1故结果常数项=0 \\
也可以这样理解:若常数项 \ne0,将其泰勒展开的话常数项始终非0,需要无穷项,无法收敛 \\
根据链式法则,(ln A(x))’=\frac{A’(x)}{A(x)},lnA(x)=C+\int \frac{A’(x)}{A(x)},这里C=0 \\
至于求exp,f(x)=A-lnx,f’(x)=-1/x,B_p=B_{\lceil p/2 \rceil}(A+1-ln B_{\lceil p/2 \rceil}) \\
$$

多项式三角函数

不会告辞

多点求值(常数13)

不会告辞

题:快速阶乘算法uoj182「UR #12」a^-1 + b problem

快速插值(常数16)

不会告辞

求幂

求ln后乘指数,exp即可,不写了,luogu模板加强版记得处理a0=0

全家福

花费了一天各种测试搞出来的,兼顾好看(自然语言+短)以及速度

注意:做题一定要写const int MOD,本机10s->3s,洛谷7s->2s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
namespace PP//全家桶板子
{
const int LN=1<<19;int inv[LN+1];
struct NTT
{
vc<int> w[30];NTT(){inv[1]=1;for(int i=2;i<=LN;i++) inv[i]=ll(MOD-MOD/i)*inv[MOD%i]%MOD;
for(int i=1;i<=20;i++) {w[i].resize(bin(i));w[i][0]=1;int pp=qpower(3,(MOD-1)/bin(i));for(int j=1;j<bin(i-1);j++) w[i][j]=1ll*w[i][j-1]*pp%MOD;}
}
int R[LN];inline void DFT(int A[],int lg,int op=0)
{
int m=bin(lg);assert(m<=LN);if(op) reverse(A+1,A+m);
for(int i=1;i<m;i++){R[i]=(R[i>>1]>>1)|((i&1)<<(lg-1));if(R[i]<i)swap(A[i],A[R[i]]);}
for(int ln=1,lgg=1;ln<m;ln<<=1,lgg++) for(int st=0;st<m;st+=2*ln) for(int k=0;k<ln;k++)
{int t=1ll*w[lgg][k]*A[st+ln+k]%MOD;A[st+ln+k]=mm(A[st+k]+MOD-t);A[st+k]=mm(A[st+k]+t);}
}
}ntt;
int _A[LN],_B[LN],_C[LN],M;
struct P//此结构体内函数选择性写
{
vc<int> a;int n;void rs(int nn){a.resize(n=nn);}P(){rs(M);}
int& operator [] (int x){return a[x];}
friend const P operator * (P a,const int &b) {for(int i=0;i<a.n;i++) a[i]=(ll)a[i]*b%MOD;return a;}
inline void dft(int _A[],int lg,int ln){for(int i=0;i<bin(lg);i++)_A[i]=(i<min(ln,n)?a[i]:0);ntt.DFT(_A,lg);}
inline void idft(int _A[],int lg,int ln){ntt.DFT(_A,lg,1);rs(ln);for(int i=0;i<ln;i++)a[i]=1ll*_A[i]*inv[bin(lg)]%MOD;}
const P Mul(P b,int ln=M)
{
int lg=ceil(log2(ln+ln-1)),m=bin(lg);dft(_A,lg,ln);b.dft(_B,lg,ln);
for(int i=0;i<m;i++) _B[i]=1ll*_A[i]*_B[i]%MOD;b.idft(_B,lg,ln);return b;
}
const P operator * (const P b) {return Mul(b);}
};
void Inv(P &a,P &b,int ln=M)
{
if(ln==1){b.rs(1);b[0]=invm(a[0]);return;}Inv(a,b,(ln+1)/2);
int lg=ceil(log2(ln+ln-1)),m=bin(lg);a.dft(_A,lg,ln);b.dft(_B,lg,ln);
for(int i=0;i<m;i++) _B[i]=(2+MOD-1ll*_B[i]*_A[i]%MOD)*_B[i]%MOD;b.idft(_B,lg,ln);
}
P Ji(P a){a.rs(a.n+1);for(int i=a.n-1;i>=1;i--)a[i]=1ll*a[i-1]*inv[i]%MOD;a[0]=0;return a;}
P Dao(P a){for(int i=0;i<a.n-1;i++)a[i]=1ll*a[i+1]*(i+1)%MOD;a.rs(a.n-1);return a;}
P Ln(P &a,int ln=M){P b;Inv(a,b,ln);return Ji(Dao(a).Mul(b,ln-1));}
void Exp(P &a,P &b,int ln=M)
{
if(ln==1){b.rs(1);b[0]=1;return;}Exp(a,b,(ln+1)/2);
P pp=Ln(b,ln);for(int i=0;i<ln;i++) pp[i]=mm(a[i]+MOD-pp[i]);pp[0]++;
int lg=ceil(log2(ln+ln-1)),m=bin(lg);pp.dft(_A,lg,ln);b.dft(_B,lg,ln);
for(int i=0;i<m;i++) _B[i]=1ll*_A[i]*_B[i]%MOD;b.idft(_B,lg,ln);
}
void Sqrt(P &a,P &b,int ln=M)
{
if(ln==1){b.rs(1);b[0]=1;return;}Sqrt(a,b,(ln+1)/2);P tmp=b*2,c;Inv(tmp,c,ln);
int lg=ceil(log2(ln+ln-1)),m=bin(lg);a.dft(_A,lg,ln);b.dft(_B,lg,ln);c.dft(_C,lg,ln);
for(int i=0;i<m;i++) _A[i]=ll((ll)_B[i]*_B[i]+_A[i])%MOD*_C[i]%MOD;b.idft(_A,lg,ln);
}
P Rev(P a){reverse(a.a.begin(),a.a.end());return a;}
P Inv(P a,int ln=M){P b;Inv(a,b,ln);return b;}
P Div(const P &a,const P &b){return Rev(Rev(a).Mul( Inv(Rev(b),a.n-b.n+1),a.n-b.n+1 ) );}

P Mul2(P a,P b){M=a.n+b.n-1;return a*b;}
P DandC(vc<P> &A,int l,int r)
{
if(l==r) return A[l];
int mid=(l+r)/2;
return Mul2(DandC(A,l,mid),DandC(A,mid+1,r));
}
};

拉格朗日插值

众所周知,n+1个横坐标不同的点能唯一确定一个n次多项式,现在就是求这个多项式

拉格朗日基本多项式 :$\ell_i(x)=\prod_{j=0,i!=j}^n \frac{x-x_j}{x_i-x_j}$

注意到有些不错的性质:$\ell_i(x_i)=1,\ell_i(x_j)=0,\forall j \ne i$ (有一点点中国剩余定理的感觉)

于是可以构造出多项式 $P=\sum_{i=0}^n y_i\ell_i(x)$

已经可以做到$n^2$,配合多项式多点求值和插值可以做到$O(nlog^2n)$ 然而我不会,听说常数巨大

重心拉格朗日插值:

稍微思考一下就会发现可以维护公共部分,需要的时候除掉,这样就可以O(n)插入了

另外你会发现你可以耍赖地切构造题了,abc137f Polynomial Construction

讲题前说个事,题目中比较常见的多项式形式是 $\sum_{x=1}^n (\sum_{j=0}^k a_jx^j)$ 然后这个整体也是个关于n的多项式,系数为n+1,这个的话我现在写成这样一定很显然(交换和号然后就是自然数幂和),不过通常后面是个隐蔽的多项式

bzoj2655 calc

做法一:

设$f(i,j)$ 表示前i个数,选了j个(有序选,最后乘n!)

$f(i,j)=f(i-1,j)+i*f(i,j-1)或f(i,j)=i \sum_{k=0}^{i-1} f(k,j-1)=i*s(i-1,j-1)$

第二种的形式更舒适,观察第二种,盲猜一手可知,如果以i为未知数,应该是一个最高2j次的多项式,其中前缀和贡献+1,乘i贡献+1,当然你也可以打表

因此把前面的dp预处理好,然后拉格朗日插值,时间复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll f[N][N],s[N][N],fac[N],facinv[N];
void main()
{
int A=qread(),n=qread();MOD=qread();
fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%MOD;
facinv[N-1]=invm(fac[N-1]);for(int i=N-2;i>=0;i--) facinv[i]=facinv[i+1]*(i+1)%MOD;

s[0][0]=1;
for(int i=1;i<=n+n;i++)
{
f[i][0]=s[i][0]=1;
for(int j=1;j<=i;j++) f[i][j]=s[i-1][j-1]*i%MOD,s[i][j]=(s[i-1][j]+f[i][j])%MOD;
}
if(A<=n+n){write(s[A][n]*fac[n]%MOD);return;}
ll all=1;for(int i=0;i<=n+n;i++) all=all*(A-i)%MOD;
ll ans=0;
for(int i=n;i<=n+n;i++)
{
ll tmp=all*invm(A-i)%MOD;
tmp=tmp*facinv[i]%MOD*facinv[n+n-i]%MOD;if((n+n-i)&1) tmp=-tmp;
ans=(ans+tmp*s[i][n]%MOD*fac[n]%MOD)%MOD;
}
write((ans+MOD)%MOD);
}//x+MOD

做法二:倍增,并不是很会,见这里

做法三:lcxer的容斥
$$
f(n)表示长度为n序列的方案的权值和,g(n,x)表示长度为n且包含元素x的权值和 \\
每种都被统计n次,f(n)=\frac{1}{n} \sum_{i=1}^A g(n,i);
然后g很好容斥,g(n,x)=\sum_{i=1}^n (-1)^{i-1} x^i f(n-i) \\
f(n)=\frac{1}{n} \sum_{k=1}^n (-1)^{k-1} f(n-k) (\sum_{i=1}^A i^k) ,每个合法序列只会以某种顺序统计一次,最后乘n!
$$
做法四:WorldWide_D的容斥

bzoj4559 JLoi2016 成绩比较

$$
f(i,j)表示考虑前i门课,j个人目前被碾压,f(i,j)=(\sum_{x=1}^{u_i} x^{n-r_i}(u_i-x)^{r_i-1}) \sum_{k=j}^n f(i-1,k)C_k^jC_{n-k}^{n-r_i-j}
$$

前面那个插值即可,预处理幂后复杂度为 $O(n^3)$ code

另一种做法是注意到分数的选择跟大小方案无关,容斥出大小方案个数,乘以分数选择方案(且m门课程独立),分数选择方案也可以插值或递推,详见CQzhangyu

下降幂多项式

$F(x)=\sum_{i=0}^{\infty} f_i x^{\underline i}$

当给出连续点值的时候,会有一个不错的性质

看到点值连续考虑点值的生成函数G,$a^{\underline b}(a<b)=0$

$G(x)=\sum_i f(i) \frac{x^i}{i!}=\sum_j f_j(\sum_{i=j} \frac{i^{\underline j}x^i}{i!})=\sum_j f_j x^j (\sum_{i=j} \frac{x^{i-j}}{(i-j)!})=FF*e^x$,注意这里FF是个OGF而G是EGF

所以当一个多项式给出连续点值的时候,可以在nlogn内求出多项式的下降幂形式(不用求逆,$e^{-x}$直接得系数),如果只有原多项式则多点插值(虽然我不会)

例题:uoj269 「清华集训2016」如何优雅地求和

一些技巧

  1. 给出n-1次多项式A,n个1次多项式$B_i$,对$\forall i求 A \% B_i$;直接做$O(n^2)$,但是多项式取模有个性质:

    $当C \bmod B_i=0时,A \bmod B_i=(A \bmod C) \bmod B_i$,考虑分治,$solve(l,r)时求出A \bmod (\prod_{i=l}^{mid} B_i),右边也是一样,分治做下去,T(n)=2T(n/2)+O(nlogn)=O(nlog^2n)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8c82.html
转载请注明出处,谢谢!