【正文】 x^(t+1))/(1x)。 pku3487 The Stable Marriage Problem zoj1576 Marriage is Stable 14. 數(shù)位類(lèi)統(tǒng)計(jì)問(wèn)題 在航點(diǎn)月賽中第一次接觸到這類(lèi)問(wèn)題，scau 大牛little 龍推薦我看了一篇論文，09 年劉聰?shù)摹稖\談數(shù)位類(lèi)統(tǒng)計(jì)問(wèn)題》，這篇論文相當(dāng)精彩，也相當(dāng)詳 細(xì)，每道題都有詳細(xì)的分析和作者的參考代碼。 樹(shù)狀數(shù)組 hdu 3333 先求出每個(gè)位置后面和它一樣的最近的那個(gè)數(shù)的位置next[i] ，然后用樹(shù)狀數(shù)組記錄不重復(fù)的前n 個(gè)數(shù)的和，接著對(duì)詢(xún) 問(wèn)區(qū)間排序，從左到右做，記left 為在當(dāng)前區(qū)間左邊的那些數(shù)，通過(guò)樹(shù)狀數(shù)組，將left 到next[left]1 之間的所有的數(shù)都減去 val[left] ，然后就可以直接像sum[i]sum[j] 那樣方便的求出區(qū)間里面沒(méi)有重復(fù)的數(shù)的和。結(jié)果就是 2^(dig[2]dig[5])*3^(dig[3])*7^(dig[7])*9^(dig[9]) mod 10 ，用快速冪乘來(lái)算。如果每次重復(fù)的數(shù)，輸出c[n][m]就可以。原文如下： Using a Sierpiński triangle, it39。這樣搜索的空間就只有n的剩余系了。 pku 1737 Connected Graph(組合數(shù)學(xué)，高精度) 題目是求n個(gè)點(diǎn)用邊鏈接，形成聯(lián)通圖的方案總算?？紤]一個(gè)完整的聯(lián)通圖，可以標(biāo)記兩個(gè)點(diǎn)1，2。將他們乘在一起就有了上面的式子。題目還要求mod 9901,這雖然是個(gè)素?cái)?shù)，但是數(shù)據(jù)中出現(xiàn)了p1 = 0 (mod 9901)的情況，這時(shí)f(p^t)=t+1 (mod 9901),要特殊處理下，其余用快速冪乘。那么只有統(tǒng)計(jì)出所有點(diǎn)的組合情況就可以得出答案了。 為了找S的一組解，可以把S變小，來(lái)得到S的解。更重要的是當(dāng)S一定大時(shí)，一定會(huì)有解。 pku 2142 The Balance(不定方程) 不定方程題，解a*x+b*y=d 。*x+b39。t。 pku 3352 In Danger(約瑟夫環(huán)) 簡(jiǎn)單題，和具體數(shù)學(xué)第一章提到的問(wèn)題是一樣的，講每數(shù)2去掉一人，求勝利人的編號(hào)。 for(i=0。 tmp=(a/times)%10。itmp。 } pku 2429 gcd lcm Inverse 大數(shù)分解，要分解的數(shù)很大，到了2^63,普通的素?cái)?shù)表方法行不通，要使用Pollard分解，分解lcm/gcd。先求出任意兩個(gè)數(shù)的差(要正的),找個(gè)最小的數(shù)，使其不是前面求的差的約數(shù)。c=a1 (mod b1),c=a2 (mod b2) c=a1+b1*x, a1+b1*x= a2 (mod b2),用擴(kuò)展歐幾里德求出c。在較大數(shù)的每一個(gè)等價(jià)類(lèi)中找出最小的一數(shù)，它是較小數(shù)的倍數(shù)，那么在這個(gè)等價(jià)類(lèi)中小于這個(gè)數(shù)的都是不能被表示出來(lái)的。矩陣的n冪模，和快速冪乘的原理是一樣的。 pku2992 Divisors (組合數(shù)，因子個(gè)數(shù)) 計(jì)算C(n,k)的因子個(gè)數(shù),由于n很小，最大為431，所以可以把1～431的所有數(shù)先因式分解，再來(lái)統(tǒng)計(jì)n*(n1)...(nk+1)/k*(k1)...1的素因子個(gè)數(shù)。 pku 3128 Leonardo39。 pku 3244 Difference between Triplets(公式變形) 很巧妙的公式變形，可惜不自己想出來(lái)的。這里要用小于O(n^2)的算法，把數(shù)組排序后可以拿掉絕對(duì)值，統(tǒng)計(jì)每個(gè)元素作為減數(shù)出現(xiàn)的次數(shù)。這樣比直接模運(yùn)算要快。 pku 3516 Hide That Number（高精度） 題目是說(shuō)給出一個(gè)數(shù)y，找到 x*11= y (mod 10^length(y)),如果y很小，直接求出逆來(lái)就能得到答案了，可是y很大，構(gòu)造的方法沒(méi)有想到，最后還是暴力做的。 pku 3847 The Stable Marriage Problem（穩(wěn)定婚姻） 穩(wěn)定婚姻問(wèn)題。 pku 3358 Period of an Infinite Binary Expansion(數(shù)論，歐拉定理) 這個(gè)題目是求兩個(gè)數(shù)相除p/q，結(jié)果的小數(shù)部分用二進(jìn)制表示，當(dāng)q不是2的冪時(shí)，這個(gè)二進(jìn)制是個(gè)無(wú)線(xiàn)循環(huán)的01串。然后從1開(kāi)始枚舉，所以的歐拉數(shù)的因子。q)==2){ pr(0.)。 pr(%d,p/q)。一個(gè)置換可以分解成多個(gè)循環(huán)，每次置換元素之和在同一個(gè)循環(huán)中的元素發(fā)生轉(zhuǎn)換，同一個(gè)循環(huán)中循環(huán)節(jié)是元素的個(gè)數(shù)，所以這個(gè)題是要把一個(gè)數(shù)分成多個(gè)數(shù)的和，讓這些數(shù)的最小公倍數(shù)最大。否則計(jì)算(a^p)%p,若結(jié)果是a輸出yes，否則輸出no。并且n是偶數(shù)時(shí)，其解是n除去2因子的解。 2008 成都網(wǎng)絡(luò)預(yù)選 1005 Farey Sequence Again(Farey Sequence ,構(gòu)造) 與其說(shuō)是數(shù)學(xué)題，還不如說(shuō)是個(gè)模擬題。這個(gè)性質(zhì)很有用，根據(jù)它可以推出序列中前n項(xiàng)的分子不超過(guò)3，而且在構(gòu)造的時(shí)候也要用到這個(gè)性質(zhì)，找個(gè)第一個(gè)分母是2和3的元素的位置，都可以通過(guò)觀察看出規(guī)律。所以的規(guī)律都可以在模擬的序列中看出。 一，當(dāng)k為p時(shí)，n=(p39。)^(p^21) 三，當(dāng)k為1是，n=1。 由于反素?cái)?shù)要求約數(shù)盡量多，所以素因子個(gè)數(shù)要盡量少，而指數(shù)要盡量大，這樣一個(gè)數(shù)成為反素?cái)?shù)的機(jī)會(huì)就大。 。轉(zhuǎn)移方程 f[i][j]= min{f[i1][j/(k+1)]*p(i)^k} f[i][j] 表示i個(gè)素?cái)?shù)，有j個(gè)約數(shù)的最小值。都是反素?cái)?shù)。)^(p1)*(p239。計(jì)算小于n的數(shù)有多少個(gè)這種數(shù)就是答案。這樣循環(huán)的。要用到的一個(gè)性質(zhì)是 Fn中連續(xù)的3個(gè)元素，a1/b1 ,a2/b2,a3/b3。枚舉歐拉數(shù)的因子，最小的那個(gè)就是要求的解。 賽后才發(fā)現(xiàn)這題并不拿，可能是我太菜了。由于數(shù)比較小，23是能最大的素?cái)?shù)，所以直接枚舉可以滿(mǎn)足。 } pr(\n)。i=100。 while(scanf(%d%d,amp。這樣轉(zhuǎn)換成一個(gè)模方程:p*2^n = x(mod q),當(dāng)然p和q要互素，2和q互素。用最優(yōu)方提出匹配，而被匹配者，不會(huì)立即接受，而是在提出要求者的集合中去掉，比當(dāng)前著差的元素，知道沒(méi)有人提出匹配，被匹配者才確定下匹配關(guān)系。若是，就可以得到答案了。要看N的二次完全剩余系是否都有解。在計(jì)算模的時(shí)候，由于是mod 2^p1,可以用移位來(lái)加速。那么 D(Ta, Tb) = max {Ia ? Ib, Ja ? Jb, Ka ? Kb} ? min {Ia ? Ib, Ja ? Jb, Ka ? Kb} =(|IaIbJa+Jb|+|JaJbKa+Kb|+|IaIbKa+Kb|)/2 令I(lǐng)aJa=Wa,JaKa=Ua,IaKa=Ha。一個(gè)置換的平方，原來(lái)偶數(shù)長(zhǎng)的循環(huán)會(huì)被分裂成兩段長(zhǎng)度相等的循環(huán)，而奇數(shù)長(zhǎng)的循環(huán)不會(huì)被分裂。也就是說(shuō)存在連續(xù)的一段al,...am,之和被m整除。統(tǒng)計(jì)x，y的對(duì)數(shù)再加1（x=z,y=z是特殊的一對(duì)）。具體的推導(dǎo)就不知道是怎么來(lái)的。= c (mod lcm(b1,b2))表示。可以通過(guò)先求 兩個(gè)方程的解，這樣就將兩個(gè)方程和并成一個(gè)，直達(dá)只剩下一個(gè)為止就可以的到答案了。 pku 2769 Reduced ID Numbers(同余) 給出n個(gè)數(shù)，找一個(gè)數(shù)p,使得沒(méi)個(gè)數(shù)mod p的值不相等。 aa[tmp]+=a%times+1。else start=1。i++)aa[i]+=len*times?？梢苑謩e計(jì)算f(b),f(a1)的大小,其中 ab f(n)表示1到n數(shù)字出現(xiàn)的統(tǒng)計(jì)。 pku 2154 Color(波利亞定理,著色問(wèn)題) 一個(gè)經(jīng)典的著色問(wèn)題，題目描述的是一個(gè)正常的旋轉(zhuǎn)群，它的輪換指標(biāo)為1/n*sigma(euler(d)*(xd)^(n/d)) ，其中d為n的所有因子。一般解為x=x0b39。a/=k,b/=k,d/=k。所以事先保留一些小的S的解。或p/2+1/3+1/6=1,p*2+9=S。 pku 1831 不定方程組(構(gòu)造解) 這個(gè)題目很有意思，說(shuō)a1+a2..an=s,1/a1+1/a2....+1/an=1。這題不要去算具體的面積，答案和所選點(diǎn)的奇偶性有關(guān)，點(diǎn)的只有4種類(lèi)型，(0,0),(1,1),(1,0),(0,1)。 pku 1845 Sumdiv(積性函數(shù)，因子和) 求a^b的因子和(包括1和a^b),由于因子和是積性函數(shù)。在g1中最少要有一個(gè)點(diǎn)與g2中的點(diǎn)2鏈接。還來(lái)在網(wǎng)上看到一種更好的解法。從最高位開(kāi)始，一位一位確定dfs下去，每次都要保證已確定的位的所有組合不少于題目給出的序號(hào)。s in binary representations of results of respective expressions: then mimic a bitwise AND operation by intersecting these two sets: to obtain the parity of a Stirling number of the second kind in O(1) time. pku 1465 Multiple(BFS,整除) 給幾個(gè)一些數(shù)學(xué)，找出由這些數(shù)字組成的數(shù)中最小的一個(gè)能整除n的數(shù)。注意幾個(gè)邊界條件，c[0][0]=1,z[1][0...a[1]]=1,z[i][1]=i 2=i=s。枚舉前一半的未知數(shù)可以到達(dá)的值(用hash表保存)，再枚舉后一半，這樣可以加快枚舉。只有各位上的數(shù)字才會(huì)影響最后一個(gè)非零數(shù)字。 簡(jiǎn)單： ural1057 Amount of degrees spoj1182 Sorted bit squence hdu3271 SNIBB 較難： spoj2319 Sequence