【正文】 //(10^n1+..+10+1)=(10^n1)/9, 歐拉函數(shù)，離散對數(shù)，注意溢出處理（相乘時變?yōu)閍T+b ）。 樹狀數(shù)組 hdu 3333 先求出每個位置后面和它一樣的最近的那個數(shù)的位置next[i] ，然后用樹狀數(shù)組記錄不重復(fù)的前n 個數(shù)的和，接著對詢 問區(qū)間排序，從左到右做，記left 為在當(dāng)前區(qū)間左邊的那些數(shù)，通過樹狀數(shù)組，將left 到next[left]1 之間的所有的數(shù)都減去 val[left] ，然后就可以直接像sum[i]sum[j] 那樣方便的求出區(qū)間里面沒有重復(fù)的數(shù)的和。 pku 3222 // 樹的dfs 和分治思想 解題報告見此： 本文來自CSDN博客，轉(zhuǎn)載請標(biāo)明出處： 繼續(xù) ： pku 1150 The Last Nonzero Digit 和計算排列數(shù)末尾有多少個零有些類似，把2，5因子都拿出來，剩下的數(shù)的最后一個數(shù)字只有1，3，7，9。只有各位上的數(shù)字才會影響最后一個非零數(shù)字。統(tǒng)計可以用遞歸來統(tǒng)計，求出1～n中因子2，5的個數(shù)，以及3，7，9結(jié)尾的數(shù)和去掉2，5后新的到的數(shù)中3，7，9結(jié)尾的數(shù)。結(jié)果就是 2^(dig[2]dig[5])*3^(dig[3])*7^(dig[7])*9^(dig[9]) mod 10 ，用快速冪乘來算。 pku 1186 方程的解數(shù) (hash,枚舉) 題目給出最多有6個未知數(shù)，未知數(shù)的取值在[1,150]之間，直接枚舉時間復(fù)雜度是150^6，這個時間不能接受。枚舉前一半的未知數(shù)可以到達(dá)的值(用hash表保存)，再枚舉后一半，這樣可以加快枚舉。 pku 1285 Combinations, Once Again（有重復(fù)的組合，dp） 對輸入的數(shù)先統(tǒng)計一下，每個數(shù)出現(xiàn)的次數(shù)。如果每次重復(fù)的數(shù)，輸出c[n][m]就可以。有重復(fù)數(shù)時，要考慮到取相同元素的情況，那么ans=sigma c[x][i]*z[s][mi] 0i=m z[i][j]表示從1到第i堆中拿j個，把重復(fù)的數(shù)字表示成a[1],a[2]..,a[s],s個數(shù)出現(xiàn)重復(fù)。注意幾個邊界條件，c[0][0]=1,z[1][0...a[1]]=1,z[i][1]=i 2=i=s。 pku 1430 Binary Stirling Numbers (stirling 數(shù)) 在wiki上找到公式，原來mod 2時和組合數(shù)有關(guān)系。原文如下： Using a Sierpiński triangle, it39。s easy to show that the parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient: Or directly, let two sets contain positions of 139。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,整除) 給幾個一些數(shù)學(xué)，找出由這些數(shù)字組成的數(shù)中最小的一個能整除n的數(shù)。0n4999,把所有的數(shù)從小到大開始，在入隊(duì)列前看下該數(shù)所到達(dá)的余數(shù)是否被前面小的數(shù)求到過，若否才入隊(duì)。這樣搜索的空間就只有n的剩余系了。 pku 1715 Hexadecimal Numbers(組合) 不重復(fù)的組合問題，知道第幾個找出這個組合。從最高位開始，一位一位確定dfs下去，每次都要保證已確定的位的所有組合不少于題目給出的序號。最多八層。 pku 1737 Connected Graph(組合數(shù)學(xué)，高精度) 題目是求n個點(diǎn)用邊鏈接，形成聯(lián)通圖的方案總算。滿足聯(lián)通的邊數(shù)在[n1,n(n1)/2],自己一開始想分邊數(shù)情況考慮，發(fā)現(xiàn)情況比較復(fù)雜，推出一個像整數(shù)拆分的方法。還來在網(wǎng)上看到一種更好的解法。公式是f[n]=f[k]*f[nk]*c[n2][k1]*((2^k)1) (c[n2][k]表示組合數(shù),1=kn)?？紤]一個完整的聯(lián)通圖，可以標(biāo)記兩個點(diǎn)1，2。將點(diǎn)1，點(diǎn)2分別劃分在兩個子聯(lián)通圖中分別為g1，g2。在g1中最少要有一個點(diǎn)與g2中的點(diǎn)2鏈接。這樣的方式共2^k1中，而g1總有c[n2][k1]個。將他們乘在一起就有了上面的式子。另外這題要用到高精度，終于用java寫了個高精度的題感覺真方便。 pku 1845 Sumdiv(積性函數(shù)，因子和) 求a^b的因子和(包括1和a^b),由于因子和是積性函數(shù)。所以f(a^b)=f(p1^t1)*f(p2^t2)...*f(pn^tn),對于f(p^t)的情況: f(p^t)=1+p+p^2+...+p^t=(p^(t+1)1)/p1。題目還要求mod 9901,這雖然是個素數(shù)，但是數(shù)據(jù)中出現(xiàn)了p1 = 0 (mod 9901)的情況，這時f(p^t)=t+1 (mod 9901),要特殊處理下，其余用快速冪乘。 pku 1809 Regetni（奇偶，組合） 根據(jù) 這個公式計算 A=|x1y2 y1x2 + x2y3 y2x3 + x3y1 y3x1|/2 三角形的面積是否為整數(shù)。這題不要去算具體的面積，答案和所選點(diǎn)的奇偶性有關(guān)，點(diǎn)的只有4種類型，(0,0),(1,1),(1,0),(0,1)。把這4類點(diǎn)的所有組合情況(共20種)代入公式 發(fā)現(xiàn)，當(dāng)最少有兩個點(diǎn)屬于同一類型是面積才是整數(shù)。那么只有統(tǒng)計出所有點(diǎn)的組合情況就可以得出答案了。點(diǎn)的組合情況 {0,1,2},{0,1,3},{0,2,3},{1,2,3},{0,1,1},{0,2,2},{0,3,3},{1,0,0},{1,2,2},{1,3,3},{2,0,0},{2,1,1},{2,3,3}, {3,0,0},{3,1,1},{3,2,2},{0,0,0},{1,1,1},{2,2,2},{3,3,3} 這些是合理的組合。 pku 1831 不定方程組(構(gòu)造解) 這個題目很有意思，說a1+a2..an=s,1/a1+1/a2....+1/an=1。求一組這樣的解。 為了找S的一組解，可以把S變小，來得到S的解。兩種變小的方法:p/2+1/2=1 ,p*2+2=S。或p/2+1/3+1/6=1,p*2+9=S。選這兩種方式是為了使奇數(shù)，偶數(shù)都有變小的方法。更重要的是當(dāng)S一定大時，一定會有解。證明可以通過歸納來證得。所以事先保留一些小的S的解。大的S通過遞歸的構(gòu)造出解來。 pku 2142 The Balance(不定方程) 不定方程題，解a*x+b*y=d 。先求a*x0+b*y0=k。a/=k,b/=k,d/=k。 得到等價方程a39。*x+b39。*y=d39。，一般解為x=x0b39。*t,y=y0+a39。t。其中t為任意整數(shù)。 pku 2154 Color(波利亞定理,著色問題) 一個經(jīng)典的著色問題，題目描述的是一個正常的旋轉(zhuǎn)群，它的輪換指標(biāo)為1/n*sigma(euler(d)*(xd)^(n/d)) ，其中d為n的所有因子。有了這個生成函數(shù)就可以容的計算n種顏色，在正n邊形上著色的不同方案數(shù)了。 pku 3352 In Danger(約瑟夫環(huán)) 簡單題，和具體數(shù)學(xué)第一章提到的問題是一樣的，講每數(shù)2去掉一人，求勝利人的編號。公式是 f(n)=f(n/2)*21 n=2*k f(n)=f(n1/2)*2+1 n=2*k+1 pku 2282 The Counting Problem(計數(shù)統(tǒng)計) 一個計算問題，統(tǒng)計a,b之間09這些數(shù)字出現(xiàn)的次數(shù)?？梢苑謩e計算f(b),f(a1)的大小,其中 ab f(n)表示1到n數(shù)字出現(xiàn)的統(tǒng)計。對于f(n) ，可以按位計算，從個位到n的最高位，分別計算09的個數(shù)，0的計算有些特殊，因?yàn)?不能是一個數(shù)字的最高位 while(a=times) { len=a/(times*10)。 for(i=0。i10。i++)aa[i]+=len*times。 if(len0)aa[0]=times。 tmp=(a/times)%10。 if(a=times*10)start=0。else start=1。 for(i=start。itmp。i++)aa[i]+=times。 aa[tmp]+=a%times+1。 times*=10。 } pku 2429 gcd lcm Inverse 大數(shù)分解，要分解的數(shù)很大，到了2^63,普通的素數(shù)表方法行不通，要使用Pollard分解，分解lcm/gcd。需要注意的是會出現(xiàn)lcm==gcd的情況。 pku 2769 Reduced ID Numbers(同余) 給出n個數(shù)，找一個數(shù)p,使得沒個數(shù)mod p的值不相等。即n個數(shù)mod p不同余。先求出任意兩個數(shù)的差(要正的),找個最小的數(shù)，使其不是前面求的差的約數(shù)。 pku 2891 Strange Way to Express Integers(解模線性方程組) 這題是解個同余方程組，既解x= ai (mod bi) ,題目沒有保證bi之間兩兩互素，所以中國剩余定理，在這里沒用?？梢酝ㄟ^先求 兩個方程的解，這樣就將兩個方程和并成一個，直達(dá)只剩下一個為止就可以的到答案了。在合并的過程中有不能合并的情況出現(xiàn)就 說明整個方程組沒有解。c=a1 (mod b1),c=a2 (mod b2) c=a1+b1*x, a1+b1*x= a2 (mod b2),用擴(kuò)展歐幾里德求出c。兩個方程就 可以用 c39。= c (mod lcm(b1,b2))表示。 hdu 1792 A New Change