多项式及求和_By_浙江省镇海中学_杜瑜皓_(OI-WC2013)

多项式及求和杜瑜皓浙江省镇海中学January26,2013首先我们来看一个问题nidmodmi=0首先我们来看一个问题nidmodmi=0d≤50,n≤1018,m≤1018首先我们来看一个问题nidmodmi=0d≤50,n≤1018,m≤1018d≤200,n≤1010000,m≤1018，m为素数首先我们来看一个问题nidmodmi=0d≤50,n≤1018,m≤1018d≤200,n≤1010000,m≤1018，m为素数d≤2000,n≤1010000,m≤1018，m为素数首先我们来看一个问题nidmodmi=0d≤50,n≤1018,m≤1018d≤200,n≤1010000,m≤1018，m为素数d≤2000,n≤1010000,m≤1018，m为素数d≤200000,n≤1010000,m≤1018，m为素数1.d≤50,n≤1018,m≤10181.d≤50,n≤1018,m≤1018我们令Sd(n)=idi=0n−11.d≤50,n≤1018,m≤1018我们令Sd(n)=idi=0构造向量Vn={Sd(n),n0,n1,...,nd}Tn−11.d≤50,n≤1018,m≤1018我们令Sd(n)=idi=0构造向量Vn={Sd(n),n0,n1,...,nd}T转移：Sd(n+1)=Sd(n)+ndn−11.d≤50,n≤1018,m≤1018我们令Sd(n)=idi=0构造向量Vn={Sd(n),n0,n1,...,nd}T转移：Sd(n+1)=Sd(n)+ndn−1i(n+1)i=j=0(i\jnj1.d≤50,n≤1018,m≤1018我们令Sd(n)=idi=0构造向量Vn={Sd(n),n0,n1,...,nd}T转移：Sd(n+1)=Sd(n)+ndn−1i(n+1)i=j=0(i\jnjVn+1=Vn∗AA是一个(d+2)∗(d+2)的矩阵，具体系数可以通过前面的转移方程得出。A是一个(d+2)∗(d+2)的矩阵，具体系数可以通过前面的转移方程得出。用矩阵乘法加快速幂优化，那么就可以在O(d3logn)的时间内解决。A是一个(d+2)∗(d+2)的矩阵，具体系数可以通过前面的转移方程得出。用矩阵乘法加快速幂优化，那么就可以在O(d3logn)的时间内解决。这里并没有除法运算，所以和m取值的关系并不大。2.d≤200,n≤1010000,m≤1018，m为素数2.d≤200,n≤1010000,m≤1018，m为素数我们可以证明Sd(n)是关于n的d+1次的多项式。2.d≤200,n≤1010000,m≤1018，m为素数我们可以证明Sd(n)是关于n的d+1次的多项式。进行一下简单的数学推导2.d≤200,n≤1010000,m≤1018，m为素数我们可以证明Sd(n)是关于n的d+1次的多项式。进行一下简单的数学推导d=0时显然成立2.d≤200,n≤1010000,m≤1018，m为素数我们可以证明Sd(n)是关于n的d+1次的多项式。进行一下简单的数学推导d=0时显然成立假设d=k时成立2.d≤200,n≤1010000,m≤1018，m为素数我们可以证明Sd(n)是关于n的d+1次的多项式。进行一下简单的数学推导d=0时显然成立假设d=k时成立当d=k+1时d(j+1)d+1−jd+1=i=0(d+1\ijid(j+1)d+1−jd+1=i=0(d+1\ijid(j+1)d+1−jd+1=i=0把j从0到n−1求和(d+1\ijin−1n−1d(j+1)d+1−jd+1=j=0j=0i=0(d+1\ijid(j+1)d+1−jd+1=i=0把j从0到n−1求和(d+1\ijin−1n−1d(j+1)d+1−jd+1=j=0j=0i=0(d+1\iji也就是dnd+1=i=0(d+1\iSi(n)d(j+1)d+1−jd+1=i=0把j从0到n−1求和(d+1\ijin−1n−1d(j+1)d+1−jd+1=j=0j=0i=0(d+1\iji也就是dnd+1=i=0(d+1\iSi(n)即(d+1)∗Sd(n)=nd+1−i=0d−1(d+1\jSi(n)(d+1)∗Sd(n)=nd+1−i=0d−1(d+1\jSi(n)(d+1)∗Sd(n)=nd+1−d−1(d+1\i=0jSi(n)右边显然是一个次数不超过d+1次的多项式，并且通过这个式子我们可以递推算出Sd(n)。(d+1)∗Sd(n)=nd+1−d−1(d+1\i=0jSi(n)右边显然是一个次数不超过d+1次的多项式，并且通过这个式子我们可以递推算出Sd(n)。时间复杂度为O(d3+logn)。3.d≤2000,n≤1010000,m≤1018，m为素数我们定义伯努利数xex−1=n=0∞Bnn!xn3.d≤2000,n≤1010000,m≤1018，m为素数我们定义伯努利数xex−1=n=0∞Bnn!xn定义伯努利多项式∞βn(t)xn=xn=0n!ex−1n=0n!n=0etx=(Bnxn)(txn)∞∞nn!3.d≤2000,n≤1010000,m≤1018，m为素数我们定义伯努利数xex−1=n=0∞Bnn!xn定义伯努利多项式∞βn(t)xn=xn=0n!ex−1n=0n!n=0etx=(Bnxn)(txn)∞∞nn!也就是nβn(t)=k=0(n\kBn−ktk∞βn(t+1)−βn(t)xn=xen=0n!(t+1)xtxex−1−ex−1xe=xetx(ex−1)ex−1=xetx=xn=0∞tnn!xn∞βn(t+1)−βn(t)xn=xen=0n!(t+1)xex−1−ex−1xetx=xetx(ex−1)ex−1=xetx=xn=0∞tnn!xn观察两边xn+1的系数，即得βn+1(t+1)−βn+1(t)=t(n+1)!n!n∞βn(t+1)−βn(t)xn=xen=0n!(t+1)xex−1−ex−1xetx=xetx(ex−1)ex−1=xetx=xn=0∞tnn!xn观察两边xn+1的系数，即得βn+1(t+1)−βn+1(t)=t(n+1)!n!n就是βn+1(t+1)−βn+1(t)=(n+1)tn∞βn(t+1)−βn(t)xn=xen=0n!(t+1)xtxex−1−ex−1xe=xetx(ex−1)ex−1=xetx=xn=0∞tnn!xn观察两边xn+1的系数，即得βn+1(t+1)−βn+1(t)=t(n+1)!n!n就是βn+1(t+1)−βn+1(t)=(n+1)tn所以Sd(n)=βd+1(n)−βd+1(0)d+1经化简可得m−1kn=k=01n+1n(n+1\Bmn+1−kk=0kk经化简可得m−1kn=k=0k=01n+1kn(n+1\Bmn+1−kk在这个式子中，令m=1且nl=0，那么就有nk=0(n+1\kBk=0⇒Bn=−1n+1n−1(n+1\k=0kBk经化简可得m−1kn=k=0k=01n+1kn(n+1\Bmn+1−kk在这个式子中，令m=1且nl=0，那么就有nk=0Bk=0⇒Bn=−(n+1\kn+11n−1(n+1\k=0kBk另外证明可以参见顾宇宙大神JZPKIL的题解或《具体数学》于是我们可以在O(d2)的时间内算出伯努利数，然后算出Sd(n)时间复杂度为O(d2+logn)。4.d≤200000,n≤1010000,m≤1018，m为素数4.d≤200000,n≤1010000,m≤1018，m为素数关注Sd(x)这个多项式本身，我们可以在O(dlogd)的时间内算出Sd(1),Sd(2),...,Sd(d+1)4.d≤200000,n≤1010000,m≤1018，m为素数关注Sd(x)这个多项式本身，我们可以在O(dlogd)的时间内算出Sd(1),Sd(2),...,Sd(d+1)而确定了Sd(1),Sd(2),...,Sd(d+1)也就代表确定了这个多项式。4.d≤200000,n≤1010000,m≤1018，m为素数关注Sd(x)这个多项式本身，我们可以在O(dlogd)的时间内算出Sd(1),Sd(2),...,Sd(d+1)而确定了Sd(1),Sd(2),...,Sd(d+1)也就代表确定了这个多项式。多项式的系数能在O(d2)的时间内计算。4.d≤200000,n≤1010000,m≤1018，m为素数关注Sd(x)这个多项式本身，我们可以在O(dlogd)的时间内算出Sd(1),Sd(2),...,Sd(d+1)而确定了Sd(1),Sd(2),...,Sd(d+1)也就代表确定了这个多项式。多项式的系数能在O(d2)的时间内计算。我们定义Sd−1(x)=P(x)=akdk=0(x\k4.d≤200000,n≤1010000,m≤1018，m为素数关注Sd(x)这个多项式本身，我们可以在O(dlogd)的时间内算出Sd(1),Sd(2),...,Sd(d+1)而确定了Sd(1),Sd(2),...,Sd(d+1)也就代表确定了这个多项式。多项式的系数能在O(d2)的时间内计算。我们定义Sd−1(x)=P(x)=akdk=0(x\k经过二项式反演可得ak=(−1)k−jP(j)kj=0(k\jak=(−1)k−jP(j)kj=0(k\jak=(−1)k−jP(j)kj=0(k\j也就是ak=(−1)P(j)k!kj=0k−j(k−j)!·j!ak=(−1)k−jP(j)kj=0(k\j也就是ak=(−1)P(j)k!kj=0k−j(k−j)!·j!注意这是一个卷积的形式，我们可以用FFT在O(dlogd)的时间内算出来。ak=(−1)k−jP(j)kj=0(k\j也就是ak=(−1)P(j)k!kj=0k−j(k−j)!·j!注意这是一个卷积的形式，我们可以用FFT在O(dlogd)的时间内算出来。FFT？ak=(−1)k−jP(j)kj=0(k\jak=(−1)k−jP(j)kj=0(k\j那么就有P(n)=ak=ddk=0(n\kk=0(n\kk(−1)k−jP(j)j=0(k\j=P(j)(−1)k−jddj=0k=j(n\(k\kjd(−1)k−jk=j(n\(k\kjd=(−1)k−jk=jn!k!k!(n−k)!j!(k−j)!d=(−1)k−jk=jn!j!(n−j)!(n−k)!(k−j)!(n−j)!d=(−1)k−jk=j(n\(n−j\jk−j=(n\d−jj(−1)kk=0(n−j\kd(−1)k−jk=j(n\(k\kjd=(−1)k−jk=jn!k!k!(n−k)!j!(k−j)!d=(−1)k−jk=jn!j!(n−j)!(n−k)!(k−j)!(n−j)!d=(−1)k−jk=j(n\(n−j\jk−j=(n\d−jj(−1)kk=0(n−j\kk(−1)ii=0(n\(n\(n\i01=−+...=(n−1\0−(n\1+...=−(n−1\1++...=(n\2(n−1\2−+...=(−1)(n\3k(n−1\kd(−1)k−jk=j(n\(k\kj=(−1)d−j(n−j−1\(n\d−jjd(−1)k−jk=j(n\(k\kj=(−1)d−j(n−j−1\(n\d−jjdP(n)=(−1)d−jP(j)j=0(n−j−1\(n\d−jj=(−1)d−jP(j)(n−j−1)!n!dj=0(d−j)!(n−d−1)!(n−j)!j!=(−1)d−jP(j)n(n−1)...(n−d)dj=0(d−j)!j!(n−j)这样我们在知道P(0),P(1),...,P(d)的情况下，可以在O(d)的时间复杂度内算出P(n)这样我们在知道P(0),P(1),...,P(d)的情况下，可以在O(d)的时间复杂度内算出P(n)对于本题，Sd(n)的计算是瓶颈，注意到id是积性函数，那么只要算出那些素数的幂次就可以算出所有的id的值了。这样我们在知道P(0),P(1),...,P(d)的情况下，可以在O(d)的时间复杂度内算出P(n)对于本题，Sd(n)的计算是瓶颈，注意到id