一些數(shù)學(xué)知識Gromah寫在前面本人系已退役半年的CPC選手，難免有所生疏。聽說大家現(xiàn)在水平還不錯，我就講點我認為有點小難度的東西吧。如果會了或者不想聽，可以睡覺，但不要打呼嚕。。一些定理和公式一些定理和公式費馬小定理：aododododp，其中g(shù)cda,p≠1,b>=φp一些數(shù)論函數(shù)知識φn歐拉函數(shù)，等于中與n互質(zhì)的數(shù)的個數(shù)，一般可以這樣算：φn=n1-1/p11-1/p21-1/p，其中p1,p2,,p是n的所有不同的質(zhì)因子還有：Σd|nφd=n。想想怎么證明？或者怎么理解這個式子？μn莫比烏斯函數(shù)，不妨設(shè)n=p1q1p2q2pq，那么：1μ1=1，2如果所有的q都等于1，則μn=-1，3否則μn=0有：Σd|nμd=，Σd|nd*μn/d=φd。想想怎么證明？一些數(shù)論函數(shù)知識Σd|1μd=μ1=1=對于n>1，不妨設(shè)n=p1q1p2q2pq，可知n有Σi=0,2,C,i個約數(shù)的μ值為1，有Σi=1,3,C,i個約數(shù)的μ值為-1，兩者個數(shù)相等，故Σd|nμd=0。莫比烏斯反演：如果Fn=Σd|nfd，那么fn=Σd|nFd*μn/d一些數(shù)論函數(shù)知識積性函數(shù)：對于gcda,b=1的正整數(shù)a,b，滿足fab=fa*fb的函數(shù)，比如φn，μn，dn約數(shù)個數(shù)函數(shù)等。。完全積性函數(shù)：對于任意兩個正整數(shù)a,b，滿足fab=fa*fb，比如idnidn=n等。。狄利克雷卷積：hn=Σd|nfdgn/d，稱hn是fn和gn的狄利克雷卷積一個定理：兩個積性函數(shù)的狄利克雷卷積所得到的函數(shù)仍然是積性函數(shù)。一些數(shù)論函數(shù)知識杜教篩（可能都會吧？就隨便講講好了）杜教篩大概是可以算一些特定積性函數(shù)前綴和的算法，以φ為例：所以可以從n遞歸到floorn/i，眾所周知總共只有sqrtn個結(jié)果，用記憶化搜索復(fù)雜度是On3/4，如果預(yù)處理前n2/3的結(jié)果再記憶化復(fù)雜度就變成On2/3了。一些數(shù)論函數(shù)知識給一個n，求∑i=1,2,,nμin。1<=n<=109。設(shè)Fn,m=∑i=1,2,,mμin，那么有：類歐幾里得算法歐幾里得算法？輾轉(zhuǎn)相除！類歐幾里得算法？輾轉(zhuǎn)相除類似物！類歐幾里得算法直線下整點計數(shù)給定n,p,q,a，求1<=n,p,q<=109,0<=a<q類歐幾里得算法當(dāng)p>=q時，當(dāng)p<q時，如果b>=p注意處理一下可以用幾何方法，從直線翻轉(zhuǎn)的角度推出這個式子結(jié)束條件是p=0，ifp==0return0;類歐幾里得算法最小跨區(qū)間整數(shù)給定a,ba<b，求最小的正整數(shù)，使得存在一個正整數(shù)，a<=<=b可以二分答案直線下整點計數(shù)，復(fù)雜度是Olog2的。有沒有復(fù)雜度是Olog的做法？類歐幾里得算法當(dāng)1<=a<b的時候，可以令a,b都減去當(dāng)a=0或者a<1<=b的時候，=1當(dāng)a<b<1的時候，a<=<=b,1/b<=1/<=1/a,/b<=<=/a此時1<1/b<1/a，回歸情況1，因為最小等價于最小，所以可以這樣轉(zhuǎn)化，此時=ceil/b兩個系數(shù)的差值：b-a=>1/a-1/b=b-a/ab，放大了1/ab倍，迭代n次則可以看作放大1/abn倍，這里是假設(shè)每次放大的倍數(shù)是個常數(shù)，當(dāng)差值>1時算法必然結(jié)束，復(fù)雜度大概是Olog的。類歐幾里得算法ByteDance-MoscowWorshop2020FinalContest-Reduction給一個分?jǐn)?shù)a/b，你每次可以對一個非零分?jǐn)?shù)進行如下操作：1把它變成-1/2把它變成1問你需要最少多少步才能把a/b變成0，輸出步數(shù)對1097取模的結(jié)果。a,b1e18,數(shù)據(jù)組數(shù)1e5類歐幾里得算法首先可以明確變0的策略：是正數(shù)，則變成-1/是負數(shù)，則變成1把第二步的1改成-然后暴力做？會TLE。不妨設(shè)當(dāng)前是p/q的形式，其中1-q/p=>-d/p=>p-d/p壓縮第二步之后再p/q的情況壓縮一下才是真·輾轉(zhuǎn)相除，復(fù)雜度OTloga。原根和階原根（滿足g0,g1,,godp的正整數(shù)）原根和階如何求一個數(shù)a的階？假設(shè)已知p-1=p1q1*p2q2**pq，那么一個暴力的求法是枚舉所有的質(zhì)因子，再枚舉從小到大枚舉這個因子的指數(shù)，不妨設(shè)枚舉到了piti，那么只需看a的p1q1*p2q2**piti**pq次方是否為1，如果不為1則ti，否則停止枚舉，a的階里pi的指數(shù)就是當(dāng)前ti。這里不用每次都重新算這個冪，可以把上一次的結(jié)果記下來，再求其pi次方即可。復(fù)雜度Ologp。小優(yōu)化：我們理論上對于每個i都要預(yù)處理a的次方，這個實際上是可以用分治來優(yōu)化到Ologlogp的，預(yù)處理完之后剩下的枚舉指數(shù)總復(fù)雜度是Ologp的。所以求階的復(fù)雜度可以是Ologlogp。原根和階小問題：給定b,c，求一個a，使得ab=cmododp-1，那么gq就是一個合法解。復(fù)雜度Osqrtp。拓展：如果要求出所有滿足條件的a呢？個人方法：先求出一個a，令=gcdp-1,b，s=gp-1/，那么a*s0,a*s1,a*s-1均是合法解。原根和階2019杭電多校5-Idiscretelogarithm給定odan算法的東西，我賽場上過了這個題，雖然不是這個做法，但可能本質(zhì)上差不多，我就介紹一下我的做法吧。有興趣的同學(xué)課后可以學(xué)一下這個an算法并對比一下我的做法。原根和階首先假設(shè)a和b的階相等，都等于n，不相等的情況之后再討論。不妨設(shè)n=2，則可以令a乘以An/m，這里的A表示原來輸入的a，這樣可以改變當(dāng)前位及之前的數(shù)字而不改變之后的數(shù)字，不斷地調(diào)整直到這個序列全部相等。答案就是每次的n/m的和。如果a的階na不是b的階nb的倍數(shù)，則無解，否則先把a變成ana/nb，然后同樣地做，最后答案乘以na/nb即可。復(fù)雜度OTlog2p的。單位復(fù)根眾所周知可以用abi來表示一個復(fù)數(shù)，除此之外也可以用“模長角度”的形式來表示，比如1i=√2∠45°=√2eπi/4，在計算兩個復(fù)數(shù)的乘法的時候也通常是使用這個形式，而乘法法則就是模長相乘，角度相加。單位復(fù)根就是模長為1的一組復(fù)數(shù)。比如這個方程3=1，在實數(shù)域下是只有=1這個解，但如果拓展到復(fù)數(shù)域上，則還有1∠120°和1∠240°兩個解。一般地，我們用來表示這樣的數(shù)，其中N表示方程中的冪次，即N=1，ωN=1∠360/N°=e2πi/N；i表示冪次，取值范圍是0,1,,N-1。單位復(fù)根有若干性質(zhì)，下面簡單介紹一下，某些題目就可以用到這些性質(zhì)。之前提到的原根也有類似對應(yīng)的性質(zhì)。單位復(fù)根可約性：周期性：可分性：零和性：單位復(fù)根2018ACM-IC以及一個方程nan-1n-1a1a0=0，其中方程的n個根（包括實根和復(fù)根）為1,2,,n。要求構(gòu)造一個方程ynbn-1yn-1b1yb0=0，使得方程的n個根滿足y1=1m,,yn=nm。n,m≥1,n≤6,nm≤10,|ai|≤120單位復(fù)根首先我們可以把原方程寫成-1-2-n=0的形式，那么我們不妨構(gòu)造這樣的方程：m-1mm-2mm-nm=0，可以化成：又因為nan-1n-1a1a0=-1-2-n=0，所以有：這樣我們就可以把這個方程的各項系數(shù)求出來了，不妨設(shè)為c0,c1,cmn，那么有b0=c0,b1=cm,,bn-1=cmn-1，而下標(biāo)不是m倍數(shù)的ci理應(yīng)都是0。母函數(shù)一般的母函數(shù)本質(zhì)上就是一個多項式f=a0a1a22ann可以先從dp數(shù)組的角度來考慮，假設(shè)有一個問題是說給若干物品，每個物品有一個體積v，求有多少種湊法使得總體積為V。那么ai可以看作是湊成i點體積的湊法數(shù)。來了一個新物品，體積為v，那么相當(dāng)于令當(dāng)前的dp母函數(shù)乘以一個1v，顯而易見這里的1表示不選，v表示選。這個和維護dp數(shù)組本質(zhì)上是一樣的。一般用來求組合問題。母函數(shù)例題：我們要從蘋果、香蕉、橘子和梨中拿一些水果出來，要求蘋果只能拿偶數(shù)個，香蕉的個數(shù)要是5的倍數(shù)，橘子最多拿4個，梨要么不拿，要么只能拿一個。問按這樣的要求拿n個水果的方案數(shù)?？梢詫懗雒糠N水果的母函數(shù)（不妨設(shè)是一個0,1之間的數(shù)）：蘋果f=124=1/1-2=1/1-1香蕉f=1510=1/1-5橘子f=1234=1-5/1-梨f=1四個母函數(shù)乘起來就等于1/1-2，考慮1/1-=123，那么1/1-2就等于1232，其第n項系數(shù)就是n1。母函數(shù)一些擴展：1/1-的第n項為Cn-1,n，也是不定方程a1a2a=n的非負解個數(shù)。b/1-a的第n項為Cn-1,n*anb。用母函數(shù)求解數(shù)列通項（以Fibonacci數(shù)列為例）令g=22334，可知g*g=223354=g/-1可得1*g=g-,g=/1--2，可以用待定系數(shù)法化成：可知其通項公式即為指數(shù)型母函數(shù)形如的多項式?？梢韵葟目芍丶帕械慕嵌葋砜紤]，如果有3個物品分別有2,3,3個，那么其可重集排列個數(shù)就是8!/2!*3!*3!?？紤]三個物品的指數(shù)型母函數(shù)：g1=2/2!,g2=g3=3/3!可得三個指數(shù)型母函數(shù)的乘積為：h=8!/2!*3!*3!*8/8!其中h中8的系數(shù)就是可重集排列個數(shù)。一般用來求排列問題。指數(shù)型母函數(shù)一些拓展：眾所周知，這個函數(shù)對應(yīng)“一個物品可以被選任意次”e對應(yīng)“個物品，每個物品均可選任意次”，其第n項就是按照上述規(guī)則有順序地選出n個物品的方案數(shù)，等于多少呢？就是n啦。。這不就相當(dāng)于每次可以任意選擇種物品中的一個物品，從母函數(shù)的角度來看：指數(shù)型母函數(shù)一些變式：只能選偶數(shù)個物品：只能選奇數(shù)個物品：只能選的倍數(shù)個物品：，=2就是只能選偶數(shù)個物品的情況指數(shù)型母函數(shù)2019IC，求有多少個序列a1,a2,,an滿足：ai∈i=1,2,,n；對所有偶數(shù)i，其在序列中的出現(xiàn)次數(shù)也必須是偶數(shù)。1<=n<=1e18,1<=m<=200000有ceiln/2個奇數(shù)，floorn/2個偶數(shù)，所以答案就是這個函數(shù)的第n項：m不大，直接二項式定理展開然后累加每一項即可。各種變換快速傅里葉變換FFTFastFourierTransform不會寫代碼的自己課后去補。。聽接下來的內(nèi)容只要知道這個東西是一個可以用來在Onlogn的時間內(nèi)把一個多項式g變換成g'。然后兩個這樣被變換的多項式比如g',h'的點積f'=g'·h'的逆FFT的結(jié)果f就是g和h的卷積，這個結(jié)論還有名字的，叫“卷積定理”?；居猛荆核愦笳麛?shù)高精度乘法求兩個母函數(shù)的乘積FFT在信息學(xué)競賽展現(xiàn)的只是冰山一角，不要以為FFT就只是算卷積用的。。各種變換正難則反：給兩個01串s,t，對于s中所有長度為|t|的子串ss，記其權(quán)值為ss和t同時為1的位置個數(shù)。求每個長度為|t|的子串的權(quán)值。==>把t翻轉(zhuǎn)過來，和s做卷積（把s,t都看成01數(shù)組），之后就容易了給兩個非負數(shù)組A,B，數(shù)字大小不超過1e5，對于-1e5~1e5的每個數(shù)字，統(tǒng)計有多少個數(shù)對i,j，使得Ai-Bj=。==>把B中每個元素b變成1e5-b，然后分別求出A,B的母函數(shù)，拿兩個母函數(shù)做卷積，之后就容易了各種變換快速數(shù)論變換NTT（NumberTheoryTransform）與FFT十分類似，只不過FFT是復(fù)數(shù)域上進行的變換，而NTT是在模意義下的域上進行的變換。如果你對FFT的原理有些許的了解，你就會注意到里面有一個叫做單位復(fù)根的東西，NTT實際上就是把FFT中的單位復(fù)根用原根來替代了，因為原根和單位復(fù)根有著非常相似的數(shù)學(xué)性質(zhì)。最后寫出來的代碼也是差不多的?？傊詈蟮慕Y(jié)論就是NTT的模數(shù)最好是形如a*2b1的模數(shù)，其中b盡可能不小于20，比如998244353=119*2231。當(dāng)然任意模數(shù)NTT也是可以做的，只不過比較麻煩且無趣，這里就不介紹了。各種變換快速冪套FFT/NTT：給一個n次多項式g和一個m，求gm的第n項（mod998244353）做法就是類似快速冪，只不過每次的乘法就變成多項式卷積了。需要注意的是不能對g進行FFT之后自積m次然后再逆FFT回去，因為每次卷積都會使數(shù)組變大，直接自積會爆數(shù)組，所以必須老老實實每次卷積完之后把第n項之后的手動清零再去算后面的。各種變換分治FFT/NTT：給一個數(shù)列a0,a1,,an-1，指定f0=1，然后有，求fn。看起來似乎也是兩個數(shù)列的卷積，但其中的f數(shù)列是自己卷自己，所以一般的FFT/NTT并不適用，考慮分治FFT/NTT：voidSolvel,r{ifl==r-1return;Solvel,mid;Calcl,mid,r;//可以用卷積計算[l,mid給[mid,r帶來的貢獻Solvemid,r;}復(fù)雜度是Onlog2n的。各種變換多項式sao操作：多項式求逆多項式取對數(shù)多項式ep快速插值快速多點求值我猜會分治FFT/NTT就差不多了。。有興趣的課后來和我探討上述內(nèi)容各種變換快速沃爾什變換FWTFastWalshTransform和FFT差不多，也是用來算卷積的，只不過這里的卷積是位運算卷積。比如說這個就是異或卷積：FWT也是把一個數(shù)列g(shù)變換成g'，后面和FFT一樣。只不過這里的變換理解起來比FFT應(yīng)該容易得多，我就試著講一講。各種變換假設(shè)要算A={A0,A1}和B={B0,B1}的異或卷積，考慮這樣：A'0,A'1=A0A1,A0-A1,B'0,B'1=B0B1,B0-B1（FWT）C'0,C'1=A'0B'0,A'1B'1=A0B0A0B1A1B0A1B1,A0B0-A0B1-A1B0A1B1C0,C1=C'0C'1/2,C'0-C'1/2=A0B0A1B1,A0B1A1B0（逆FWT）所以如果要算長為2N的數(shù)組A,B的異或卷積，因為不同的位之間是獨立的，不妨把A看成一個只有兩個元素的數(shù)列，A0,A1,B0,A1看作兩個2N-1的數(shù)組，這樣就把一個2N的問題變成了兩個2N-1的問題，問題可以遞歸解決。各種變換voidFWTint*A,intn{int_n=n/2;ifn==1return;FWTA,_n,FWTA_n,_n;forinti=0;i<_n;i{inta=A-A=b;}}voidNFWTint*A,intn{int_n=n/2;ifn==1return;forinti=0;i<_n;i{inta=A-A=a/2,A=b/2;}NFWTA,_n,NFWTA_n,_n;}各種變換快速冪FWT