信息學(xué)營員交流

1、多項(xiàng)式及求和杜瑜皓浙江省鎮(zhèn)海中學(xué)January 26, 2013首先來看一個(gè)問題nXdi mod mi =0d 50, n 1018, m 1018d 200, n 1010000, m 1018，m為素?cái)?shù)d 2000, n 1010000, m 1018，m為素?cái)?shù)d 200000, n 1010000, m 1018，m為素?cái)?shù)1.d 50, n 1018, m 1018令n1XdS (n) =idi =0構(gòu)造向量Vn = Sd (n), n0, n1, . . . , nd T轉(zhuǎn)移：Sd (n + 1) = Sd (n) + nd iXi(n + 1)i =njjj=0Vn+1 = Vn A

2、A是一個(gè)(d + 2) (d + 2)的矩陣，具體系數(shù)可以通過前面的轉(zhuǎn)移方程得出。用矩陣乘法加快速冪優(yōu)化，那么就可以在O(d 3 log n)的時(shí)間內(nèi)解決。這里并沒有除法運(yùn)算，所以和m取值的關(guān)系并不大。2.d 200, n 1010000, m 1018，m為素?cái)?shù)可以證明Sd (n)是關(guān)于n的d + 1次的多項(xiàng)式。進(jìn)行一下簡單的數(shù)學(xué)推導(dǎo)d = 0時(shí)顯然成立假設(shè)d = k時(shí)成立當(dāng)d = k + 1時(shí) 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右邊顯然是一個(gè)次數(shù)不超過d + 1次的多項(xiàng)式，并且通過這個(gè)式子可以遞推算出Sd (n)。時(shí)間復(fù)雜度為O(d 3 + log n)。3.d 2000, n 1010000, m 1018，m為素?cái)?shù)定義伯努利數(shù)X x ex 1Bn xn=n!n=0定義伯努利多項(xiàng)式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的系數(shù)，即得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經(jīng)化簡 m1nXX1n + 1kkn =Bkmn+1kn + 1k=0k=0在這個(gè)式子中，令m = 1且n 6= 0，那么就有 nn1XXn + 1

5、1n + 1kBk = 0 Bn = Bkkn + 1k=0k=0另外證明可以參見顧宇宙大神JZPKIL的題解或具體數(shù)學(xué)于是可以在O(d 2)的時(shí)間內(nèi)算出伯努利數(shù)，然后算出Sd (n)時(shí)間復(fù)雜度為O(d 2 + log n)。4.d 200000, n 1010000, m 1018，m為素?cái)?shù)關(guān)注Sd (x )這個(gè)多項(xiàng)式本身，可以在O(d log d )的時(shí)間內(nèi)算出Sd (1), Sd (2), . . . , Sd (d + 1)而確定了Sd (1), Sd (2), . . . , Sd (d + 1)也就代表確定了這個(gè)多項(xiàng)式。多項(xiàng)式的系數(shù)能在O(d 2)的時(shí)間內(nèi)計(jì)算。定義 dXxSd1(

6、x ) = P(x ) =經(jīng)過二項(xiàng)式反演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注意這是一個(gè)卷積的形式，時(shí)間內(nèi)算出來。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 )的時(shí)間復(fù)雜度內(nèi)算出P(n)對(duì)于本題，Sd (n)的計(jì)算是瓶頸，注意到id 是積性函數(shù)，那么只要算出那些素?cái)?shù)的冪次就可以算出所有的id 的值了。由于不超過d 的素?cái)?shù)是O(d/ log d )個(gè)，而快速冪的復(fù)雜度為O(log d )，那么時(shí)間復(fù)雜度就是O(d )就在O(d )的時(shí)間內(nèi)把這個(gè)問題解決了。4.d 200000, n 1010000, m 1018m不是素?cái)?shù)，那么對(duì)組合數(shù)計(jì)算會(huì)帶來。aaa令m = p p. . . p M，其中p d + 1。12ki12kaaa可以分別求出S (n)對(duì)p , p , . . . ,

9、p , M取模，然后用12kd12k中國剩余定理進(jìn)行合并即可。對(duì)M取模可以根據(jù)上述的方法進(jìn)行處理，因?yàn)镸沒有小于d 的因子，那么(d j)!j!和M一定是互質(zhì)的，而n j一定是n, n 1, . . . , n d 中的某一個(gè)，只要約去即可。接下來要求的是Sd (n)對(duì)pa取模，令n 1 = q0pa + r 0，那么就有Sd (n) q0Sd (pa) + Sd (r 0) (mod pa)，所以只要考慮n pa時(shí)即可。PPqp1nd令n 1 = qp + r ，那么S (n) =i +di =qi =0Pn對(duì)于它的個(gè)數(shù)不超過p，也可通過暴力直接計(jì)算。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由于對(duì)pa取模，那么(ip)k 中如果k a就可以忽略。也就是 qp1q1 p1a1XX X Xd(ip)k jdkid=ki =0i =0 j=0 k=0 a1p1q1XXXdpkjdkik=kk=0j=0i =0PPp1q1dkki 兩個(gè)互相獨(dú)立，可以分開求和。kji,j=0i =0PPq1p1dk可以遞歸計(jì)算，j可以暴力預(yù)處理。i =0j=0對(duì)于每個(gè)p，時(shí)間復(fù)雜度為O(p log2 m log d + log3 m)。ppFZU A math problemCi找到一個(gè)最小的N

11、，對(duì)所有的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大神用中國剩余定理計(jì)算出N分別求Ans對(duì)PC0 , PC1 , . . . , PCk 取模的余數(shù)，然后用中國剩01余定理合并即可。k因?yàn)閎i 200，所以多出的部分可以暴力計(jì)算。PCP 1dC問題就轉(zhuǎn)化成了i 對(duì)P 取模。i =0注意d 50 log(109)，那么就有區(qū)間內(nèi)滿足P|x 都可以忽略。令p = PC , g 為p的原根。當(dāng)i 取遍0到(p) 1時(shí)，gi 取遍

12、0, p)中與p互質(zhì)的數(shù)。(p)1p1XXdgidi (mod p)i =0i =0這是一個(gè)等比數(shù)列求和，可以二分計(jì)算。當(dāng)P = 2且C 3時(shí)，原根并不存在。P c2 1令S =dici =0當(dāng)d 為奇數(shù)時(shí)，有kd + (2c k)d 0 (mod 2c )，也就是Sc 0 (mod 2c )當(dāng)d 為偶數(shù)時(shí)，有Sc 2c1(mod 2c )當(dāng)c = 0時(shí)Sc = 1，顯然成立當(dāng)c = i 時(shí)，假設(shè)成立那么就有當(dāng)c = i + 1時(shí)，kd + (2c k)d 2kd (mod 2c )，也就是Sc 2Sc1 (mod 2c )因?yàn)镾c1 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為素?cái)?shù)Orz XLk大神法1可以通過伯努利數(shù)在O(k2)的時(shí)間內(nèi)預(yù)處理，并在O(k)的時(shí)間內(nèi)算出f (x )的表達(dá)式。令k+1Xif (x ) =axii =0那么x k+1k+1xX XXXiig (x ) =aj =ajiij=1 i =0i =0j=1Px j=1由于ji 的系數(shù)可以在O(k)時(shí)間內(nèi)算出，那么g

14、 (k)的表達(dá)式可以在O(k2)時(shí)間內(nèi)算出。令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 相同的項(xiàng)前面的系數(shù)并在一起，然后利用伯努i =0利數(shù)計(jì)算，時(shí)間復(fù)雜度為O(k2)。法2可以算出f (0), f (1), . . . , f (k + 3)的值，然后就可以算出g (0), g (1), . . . , g (k + 3)的值。由

15、于g 是一個(gè)次數(shù)為k + 2的多項(xiàng)式，那么肯定能在O(k)算出g (a)，也就是能在O(k2)的時(shí)間復(fù)雜度內(nèi)算出g (a), g (a + d ), g (a + 2d ), . . . , g (a + (k + 3)d )。Pn由于g (a + id )顯然是一個(gè)關(guān)于n次數(shù)為k + 3的S (n) =i =0多項(xiàng)值，知道了S (0), S (1), . . . , S (k + 3)的值，那么就能算出S (n)。時(shí)間復(fù)雜度還是O(k2)，但是你要實(shí)現(xiàn)的僅是給定的f (0), f (1), . . . , f (d )，計(jì)算出f (n)即可。Codechef QPOLYSUM給定一個(gè)次數(shù)為d

16、 的多項(xiàng)式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互質(zhì)官方題解的復(fù)雜度為O(D(K log D + K 2 + log(M2D) + log N log M)，其中k = log(M2d )/ log(231)特殊處理Q = 0, Q = 1的情況，Q = 0時(shí)答案就是P(0)。PnQ = 1時(shí)可以先算出P(d + 1)，令P(i )，那S (n) =i =0么已經(jīng)知道S (0), S (1), . .

17、. , S (d + 1)，就可以算出S (n)的值?？疾坏扔?或1時(shí)的情況，令n1XG (n) =P(i )Q = QnF (n) F (0)ii =0其中F (n)次數(shù)為d 的一個(gè)多項(xiàng)式，這個(gè)可以通過數(shù)學(xué)歸納法得到。當(dāng)d = 0時(shí)顯然成立。當(dāng)d = k時(shí)，假設(shè)成立。Pn1i當(dāng)d = k + 1時(shí)，令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 )是一個(gè)次數(shù)為d 1的多項(xiàng)式。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為一個(gè)常數(shù)?？紤]n = 0時(shí)，Sd (n) = 0，也就是c = F (0)F (n)顯然是一個(gè)次數(shù)為d 的多項(xiàng)式，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)表示成關(guān)于F (0)的一次函數(shù)。由于F (x )是一個(gè)次數(shù)為d 的多項(xiàng)值，那么就滿足 d +1Xd + 1ii(1)F (i ) = 0i =0這就是個(gè)關(guān)于F (0)的一次方程，可以解出F (0)的值。注意到這里在遞推和解方程中涉及了除法運(yùn)算，但在模M的條件下不一定有逆元。遞推中涉及到除Q。F (i )中F (0)的系數(shù)為Qi ，那么最終方程中F (0)的系數(shù)就為 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 是滿足條件的最小的值?？梢苑謩e算出模m1, m2, m3