一些數(shù)學(xué)知識(shí)

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