信息学营员交流

1、多项式及求和杜瑜皓浙江省镇海中学January 26, 2013首先来看一个问题nXdi mod mi =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 1018令n1XdS (n) =idi =0构造向量Vn = Sd (n), n0, n1, . . . , nd T转移：Sd (n + 1) = Sd (n) + nd iXi(n + 1)i =njjj=0Vn+1 = Vn A

2、A是一个(d + 2) (d + 2)的矩阵，具体系数可以通过前面的转移方程得出。用矩阵乘法加快速幂优化，那么就可以在O(d 3 log n)的时间内解决。这里并没有除法运算，所以和m取值的关系并不大。2.d 200, n 1010000, m 1018，m为素数可以证明Sd (n)是关于n的d + 1次的多项式。进行一下简单的数学推导d = 0时显然成立假设d = k时成立当d = k + 1时 dXd + 1i(j + 1)d+1 jd+1 =jii =0 dXd + 1i(j + 1)d+1 jd+1 =把j从0到n 1求和n1jii =0 n1 dXX Xd + 1i(j + 1)d+

3、1 jd+1 =jij=0j=0 i =0也就是 dXd + 1ind +1 =Si (n)i =0即 d 1Xd + 1jd +1(d + 1) Sd (n) = nSi (n)i =0 d 1Xd + 1jd +1(d + 1) Sd (n) = nSi (n)i =0右边显然是一个次数不超过d + 1次的多项式，并且通过这个式子可以递推算出Sd (n)。时间复杂度为O(d 3 + log n)。3.d 2000, n 1010000, m 1018，m为素数定义伯努利数X x ex 1Bn xn=n!n=0定义伯努利多项式XXXn xetxex 1 (t)Bt n!nnnnnx = (x

4、 )(x )n!n!n=0n=0n=0也就是 nXnkn(t) =Bnktkk=0X(t+1)xtx (t + 1) (t)xeex 1xennntn n!x =ex 1xnn!n=0Xxetx (ex 1)= xetx = x=ex 1n=0观察两边xn+1的系数，即得tn n!n+1(t + 1) n+1(t)=(n + 1)!就是nn+1(t + 1) n+1(t) = (n + 1)t所以d+1(n) d+1(0)S (n) =dd + 1经化简 m1nXX1n + 1kkn =Bkmn+1kn + 1k=0k=0在这个式子中，令m = 1且n 6= 0，那么就有 nn1XXn + 1

5、1n + 1kBk = 0 Bn = Bkkn + 1k=0k=0另外证明可以参见顾宇宙大神JZPKIL的题解或具体数学于是可以在O(d 2)的时间内算出伯努利数，然后算出Sd (n)时间复杂度为O(d 2 + log n)。4.d 200000, n 1010000, m 1018，m为素数关注Sd (x )这个多项式本身，可以在O(d log d )的时间内算出Sd (1), Sd (2), . . . , Sd (d + 1)而确定了Sd (1), Sd (2), . . . , Sd (d + 1)也就代表确定了这个多项式。多项式的系数能在O(d 2)的时间内计算。定义 dXxSd1(

6、x ) = P(x ) =经过二项式反演akkk=0 kXkkjak =(1)P(j)jj=0 kXkkjak =(1)P(j)jj=0也就是kX(1)kjP(j)akk!=(k j)!j!可以用FFT在O(d log d )的j=0注意这是一个卷积的形式，时间内算出来。FFT？ kXkkjak =(1)P(j)jj=0那么就有 ddkXXXnnkkjP(n) =ak=(1)P(j)kkjk=0k=0j=0 ddXXnkkj=P(j)(1)kjj=0k=j XdXdnkn!k!kjkj(1)=(1)kjk!(n k)!j!(k j)!k=jk=j XdXd(n j)!nn jn!kjkj=(1

7、)=(1)j!(n j)! (n k)!(k j)!jk jk=jk=j djXnn jk(1)=jkk=0 kXnnnn 1ni(1)=+ . . . =+ . . .i0101i =0 n 1nn 1nn 1k= +. . . =+. . . = (1)1223k dXnkn j 1nkjdj(1)= (1)d jkjjk=j dXn j 1ndjP(n) =(1)P(j)d jjj=0dX (n j 1)!n!dj=(1)P(j)(d j)!(n d 1)!(n j)!j!j=0dXn(n 1) . . . (n d )dj=(1)P(j)(d j)!j!(n j)j=0这样在知道P(0

8、), P(1), . . . , P(d )的情况下，可以在O(d )的时间复杂度内算出P(n)对于本题，Sd (n)的计算是瓶颈，注意到id 是积性函数，那么只要算出那些素数的幂次就可以算出所有的id 的值了。由于不超过d 的素数是O(d/ log d )个，而快速幂的复杂度为O(log d )，那么时间复杂度就是O(d )就在O(d )的时间内把这个问题解决了。4.d 200000, n 1010000, m 1018m不是素数，那么对组合数计算会带来。aaa令m = p p. . . p M，其中p d + 1。12ki12kaaa可以分别求出S (n)对p , p , . . . ,

9、p , M取模，然后用12kd12k中国剩余定理进行合并即可。对M取模可以根据上述的方法进行处理，因为M没有小于d 的因子，那么(d j)!j!和M一定是互质的，而n j一定是n, n 1, . . . , n d 中的某一个，只要约去即可。接下来要求的是Sd (n)对pa取模，令n 1 = q0pa + r 0，那么就有Sd (n) q0Sd (pa) + Sd (r 0) (mod pa)，所以只要考虑n pa时即可。PPqp1nd令n 1 = qp + r ，那么S (n) =i +di =qi =0Pn对于它的个数不超过p，也可通过暴力直接计算。i =q qp1q1 p1q1 p1dX

10、X XX X Xd(ip)k jdkid(ip + j)d =ki =0i =0 j=0i =0 j=0 k=0由于对pa取模，那么(ip)k 中如果k a就可以忽略。也就是 qp1q1 p1a1XX X Xd(ip)k jdkid=ki =0i =0 j=0 k=0 a1p1q1XXXdpkjdkik=kk=0j=0i =0PPp1q1dkki 两个互相独立，可以分开求和。kji,j=0i =0PPq1p1dk可以递归计算，j可以暴力预处理。i =0j=0对于每个p，时间复杂度为O(p log2 m log d + log3 m)。ppFZU A math problemCi找到一个最小的N

11、，对所有的i 从0到k满足N bi (mod P )iQkpciM =i =0 iPNi =1i A mod M求Ans =保证50 A 109, k 20, 0 bi 200, N, M 109 Orz AekdyCoin大神用中国剩余定理计算出N分别求Ans对PC0 , PC1 , . . . , PCk 取模的余数，然后用中国剩01余定理合并即可。k因为bi 200，所以多出的部分可以暴力计算。PCP 1dC问题就转化成了i 对P 取模。i =0注意d 50 log(109)，那么就有区间内满足P|x 都可以忽略。令p = PC , g 为p的原根。当i 取遍0到(p) 1时，gi 取遍

12、0, p)中与p互质的数。(p)1p1XXdgidi (mod p)i =0i =0这是一个等比数列求和，可以二分计算。当P = 2且C 3时，原根并不存在。P c2 1令S =dici =0当d 为奇数时，有kd + (2c k)d 0 (mod 2c )，也就是Sc 0 (mod 2c )当d 为偶数时，有Sc 2c1(mod 2c )当c = 0时Sc = 1，显然成立当c = i 时，假设成立那么就有当c = i + 1时，kd + (2c k)d 2kd (mod 2c )，也就是Sc 2Sc1 (mod 2c )因为Sc1 2c2 (mod 2c1)，所以就有Sc 2c1(mod

13、2c )tyvj xlkxcPPx i =1x i =1k给定k, a, n, d, p，已知f (x )，f (x ) =i , g (x ) =Pn求 i =0 g (a + id ) mod pk 123, a, n, d 123456789, p = 1234567891p为素数Orz XLk大神法1可以通过伯努利数在O(k2)的时间内预处理，并在O(k)的时间内算出f (x )的表达式。令k+1Xif (x ) =axii =0那么x k+1k+1xX XXXiig (x ) =aj =ajiij=1 i =0i =0j=1Px j=1由于ji 的系数可以在O(k)时间内算出，那么g

14、 (k)的表达式可以在O(k2)时间内算出。令k+2Xig (x ) =bxii =0 nn k+2n k+2jXX XX XXjak0 (id )jk0bj (a+id )j =g (a+id ) =bjk0k0=0i =0i =0 j=0i =0 j=0 jk+2nXXXjak0 djk0i jk0=bjk0k0=0j=0i =0Pn将id 的d 相同的项前面的系数并在一起，然后利用伯努i =0利数计算，时间复杂度为O(k2)。法2可以算出f (0), f (1), . . . , f (k + 3)的值，然后就可以算出g (0), g (1), . . . , g (k + 3)的值。由

15、于g 是一个次数为k + 2的多项式，那么肯定能在O(k)算出g (a)，也就是能在O(k2)的时间复杂度内算出g (a), g (a + d ), g (a + 2d ), . . . , g (a + (k + 3)d )。Pn由于g (a + id )显然是一个关于n次数为k + 3的S (n) =i =0多项值，知道了S (0), S (1), . . . , S (k + 3)的值，那么就能算出S (n)。时间复杂度还是O(k2)，但是你要实现的仅是给定的f (0), f (1), . . . , f (d )，计算出f (n)即可。Codechef QPOLYSUM给定一个次数为d

16、 的多项式P(x )，给出P(0), P(1), . . . , P(d )Pn1imodM的值，求P(i )Q mod M。i =0n 10100000, d 20000, 0 Q, M 1018M与2, 3, . . . , d + 14互质官方题解的复杂度为O(D(K log D + K 2 + log(M2D) + log N log M)，其中k = log(M2d )/ log(231)特殊处理Q = 0, Q = 1的情况，Q = 0时答案就是P(0)。PnQ = 1时可以先算出P(d + 1)，令P(i )，那S (n) =i =0么已经知道S (0), S (1), . .

17、. , S (d + 1)，就可以算出S (n)的值。考不等于0或1时的情况，令n1XG (n) =P(i )Q = QnF (n) F (0)ii =0其中F (n)次数为d 的一个多项式，这个可以通过数学归纳法得到。当d = 0时显然成立。当d = k时，假设成立。Pn1i当d = k + 1时，令P(i )Q 。S (n) =di =0PPn1n i =1i +1P(i 1)QiQS (n) =P(i )Q=di =0Pn1ni(Q 1)S (n) = P(n1)Q +(P(i 1)P(i )Q P(1)di =0P(i 1) P(i )是一个次数为d 1的多项式。Pn1in那么(P(i

18、 1) P(i )Q 一定能被表示成Q f (x ) f (0)i =0那么Sd (n)一定能被表示成QnF (n) c，其中F (n) = (f (n) + P(n 1)/(Q 1)，c为一个常数。考虑n = 0时，Sd (n) = 0，也就是c = F (0)F (n)显然是一个次数为d 的多项式，Sd (n) = QnF (n) F (0)Pn1P(i )Q = QnF (n) F (0)iG (n) =i =0相减得G (n + 1) G (n) = P(n)Qn = Qn+1F (n + 1) QnF (n)即F (n) + P(n)P(n) = QF (n + 1) F (n) F

19、 (n + 1) =并不知道F (0)的值，但可以通过递推Q把F (1), F (2), . . . , F (d ), F (d + 1)表示成关于F (0)的一次函数。由于F (x )是一个次数为d 的多项值，那么就满足 d +1Xd + 1ii(1)F (i ) = 0i =0这就是个关于F (0)的一次方程，可以解出F (0)的值。注意到这里在递推和解方程中涉及了除法运算，但在模M的条件下不一定有逆元。递推中涉及到除Q。F (i )中F (0)的系数为Qi ，那么最终方程中F (0)的系数就为 d +1Xd + 1iii1 d +1(1)Q= (1 Q)i =0那么在解方程中涉及到(Q 1)的逆元。令M = m1m2m3，存在u, v 使得(m2m3, Q) = 1, m1|Qu,(m1m3, Q 1) = 1, m2|(Q 1)v ，u, v 是满足条件的最小的值。可以分别算出模m1, m2, m3