star 1

NC19788 Travel

題意為：將n個節點的樹分成m個連通塊，并對每個連通塊標號的方案數，
思路：初看這道題像樹形dp，但一想轉移方程和資料范圍，感覺不可解，
換成組合數學的角度，將分成m個連通塊轉化為刪去m-1條邊，顯然刪去m-1條邊的方案與分成m個連通塊的方案是一一對應的，再將連通塊標號，就是乘m的階乘了，
因此答案為：
( n ? 1 m ? 1 ) ? m ! \dbinom{n-1}{m-1}*m! (m?1n?1?)?m!

NC50039 kotori

題意：n個1-m之間的數排成一排，相鄰數不能相等的方案數，
思路：直接給公式： m ? ( m ? 1 ) n ? 1 m*(m-1)^{n-1} m?(m?1)n?1
關鍵是擴展：n個1-m之間的數排成一個圓，相鄰數不能相等的方案數，
思路：可以發現上面的公式 m ? ( m ? 1 ) n ? 1 m*(m-1)^{n-1} m?(m?1)n?1計算的是n個1-m之間的數排成一個圓且首尾不相等的方案數 a n a_n an?和n個1-m之間的數排成一個圓但首尾相等的方案數，首尾相等的情況可以看作是n-1個1-m之間的數排成一個圓的方案數 a n ? 1 a_{n-1} an?1?，
因此，擴展后的公式為 a n + a n ? 1 = m ? ( m ? 1 ) n ? 1 ( n > = 3 ) a_n+a_{n-1}=m*(m-1)^{n-1}(n>=3) an?+an?1?=m?(m?1)n?1(n>=3)
由此解得 a n a_n an?的通項公式為：
a n = ( m ? 1 ) n + ( m ? 1 ) ? ( ? 1 ) n ? 2 ( n > = 2 ) a_n=(m-1)^{n}+ (m-1)*(-1)^{n-2}(n>=2) an?=(m?1)n+(m?1)?(?1)n?2(n>=2)
a 1 = m a_1=m a1?=m
但是我們可以用更普遍的斷環成鏈的做法得出答案，同樣可以在 O ( l g n ) O(lgn) O(lgn)得出結果，
對于第一個數取k的情況，考慮 f [ i ] [ 1 ] f[i][1] f[i][1]為第i個數為k的方案數 f [ i ] [ 0 ] f[i][0] f[i][0]為第i個數不為k的方案數，轉移方程如下：
f [ 0 ] [ 1 ] = 1 f[0][1]=1 f[0][1]=1
f [ i ] [ 1 ] = f [ i ? 1 ] [ 0 ] f[i][1]=f[i-1][0] f[i][1]=f[i?1][0]
f [ i ] [ 0 ] = ( m ? 1 ) ? f [ i ? 1 ] [ 1 ] + ( m ? 2 ) ? f [ i ? 1 ] [ 0 ] f[i][0]=(m-1)*f[i-1][1]+(m-2)*f[i-1][0] f[i][0]=(m?1)?f[i?1][1]+(m?2)?f[i?1][0]
最后答案為 f [ n ] [ 1 ] ? m f[n][1]*m f[n][1]?m，用矩陣加速即可達到目標復雜度，
再擴展：洛谷P1357
這道題同樣是斷環成鏈的方法，類似上題，
首先我們預處理出所有從狀態k1轉移到k2的情況，
然后，對于每一個初始狀態 i i i，我們令 f [ 0 ] [ i ] = 1 f[0][i]=1 f[0][i]=1，其余為0，根據轉移方程：
f [ i ] [ k 2 ] = ∑ j ∈ k 1 f [ i ? 1 ] [ j ] f[i][k2]=\sum_{{j\in{k1}}}f[i-1][j] f[i][k2]=∑j∈k1?f[i?1][j]，其中k1為所有轉移到k2的狀態集合，
利用矩陣加速求得 f [ n ] [ i ] f[n][i] f[n][i]，最后答案 a n s = ∑ i = 0 2 m ? 1 f [ n ] [ i ] ans=\displaystyle\sum_{i=0}^{2^m-1}f[n][i] ans=i=0∑2m?1?f[n][i]

ICPC線上賽模擬 A

題意：求滿足 x + y + z = k ( x ∈ [ 0 , a ] , y ∈ [ 0 , b ] , z ∈ [ 0 , c ] , k ∈ [ 0 , d ] ) x+y+z=k(x\in [0,a],y \in [0,b],z \in [0,c],k \in [0,d]) x+y+z=k(x∈[0,a],y∈[0,b],z∈[0,c],k∈[0,d])的解的個數，
思路：其實在寫美麗的項鏈這題的時候已經想到了，通常求 x + y + z + … … = k x+y+z+……=k x+y+z+……=k類似的不定方程的做法都是轉化為小球磁區間的問題，但是如果加上范圍，該如何做？
直接用組合公式做？容斥做？好像都不太行，我最后便選擇了最暴力的列舉，列舉 k ? z k-z k?z的值，
但這種方法最多只能支持4個未知數的求解，該演算法復雜度隨未知數的增多呈指數型增長，
該題的擴展：
利用反演的思想將復雜度降到根號級別，
暫時還沒有想到好方法，

star 2

NC14735 美麗的項鏈

事實上這道題是一道基礎DP題，我把它擴展了一下，算是復習一下多重排列，
題意（擴展后的）：n個盒子，每個盒子中取l[i]-r[i]個數，共取m個，組成圓排列的方案數，
思路：暴搜+多重圓排列公式，
多重排列公式： n ! n 1 ! n 2 ! … … n k ! \frac{n!}{{n_1}!{n_2}!……{n_k}!} n1?!n2?!……nk?!n!?，再除個n就是圓排列的結果，

star 3

NC15251 白兔的式子

題意： f [ 1 ] [ 1 ] = 1 , f [ i ] [ j ] = a ? f [ i ? 1 ] [ j ] + b ? f [ i ? 1 ] [ j ? 1 ] ( i > = 2 , 1 < = j < = i ) f[1][1]=1,f[i][j]=a*f[i-1][j]+b*f[i-1][j-1](i>=2,1<=j<=i) f[1][1]=1,f[i][j]=a?f[i?1][j]+b?f[i?1][j?1](i>=2,1<=j<=i)求 f [ n ] [ m ] f[n][m] f[n][m]
思路：直接推空間時間雙炸，推到最后肯定推到 f [ 1 ] [ 1 ] f[1][1] f[1][1]，于是考慮能夠推得多少個 f [ 1 ] [ 1 ] f[1][1] f[1][1]即，從 ( 1 , 1 ) (1,1) (1,1)到 ( n , m ) (n,m) (n,m)有多少條路徑，找規律可得，直走 n ? m n-m n?m次，斜走 m ? 1 m-1 m?1次，直走每次乘 a a a,斜走每次乘 b b b，
于是，答案即為： ( n ? 1 n ? m ) ? a n ? m ? b m ? 1 \dbinom{n-1}{n-m}*{a}^{n-m}*{b}^{m-1} (n?mn?1?)?an?m?bm?1

NC14599 子序列

題意：給定一個小寫字母字串T求有多少長度為m的小寫字母字串S滿足，T是S的一個子序列(不需要連續)設T的長度為n
思路：直接想式子，重復情況難剔除，再想DP，空間時間雙炸，借鑒上面模擬賽A的解法，開始暴力列舉，
列舉S中剛好出現T的長度 i i i，第 i i i個字母就是T的最后一個字母，且前 i ? 1 i-1 i?1個字母不含T， [ i + 1 , m ] [i+1,m] [i+1,m]之間可以隨意放字母 2 6 m ? i 26^{m-i} 26m?i，
為前 n ? 1 n-1 n?1個字母在 i ? 1 i-1 i?1的范圍內選好位置， ( i ? 1 n ? 1 ) \dbinom{i-1}{n-1} (n?1i?1?).
最后 i ? n i-n i?n個位置怎么放，怎么處理重復情況，
顯然，第 k k k個位置上不能放之后第一個已經擺好位置的字母，于是有 2 5 i ? n 25^{i-n} 25i?n個擺法，可以證明，不會有重復的情況（其實這里可以借鑒列舉的方式，即剛好出現這個字母），
因此答案為： ∑ i = n m 2 6 m ? i ? ( i ? 1 n ? 1 ) ? 2 5 i ? n \displaystyle\sum_{i=n}^{m}26^{m-i}*\dbinom{i-1}{n-1}*25^{i-n} i=n∑m?26m?i?(n?1i?1?)?25i?n

NC15550 箱庭的股市

題意：太長了，，，
思路：先打表，找到以下的規律：
設 f [ i ] [ j ] f[i][j] f[i][j]為第 i i i天第 j j j秒的價格，
f [ i ] [ j ] = f [ i ? 1 ] [ j ] + f [ i ? 1 ] [ j ? 1 ] ( i > 1 ) f[i][j]=f[i-1][j]+f[i-1][j-1](i>1) f[i][j]=f[i?1][j]+f[i?1][j?1](i>1)
f [ i ] [ j ] = p ( i = 1 ) f[i][j]=p(i=1) f[i][j]=p(i=1)
借鑒上面白兔的式子的做法，考慮路徑數目，這里有一點不一樣，所有第一行 ( i = 1 ) (i=1) (i=1)的點都可以作為終點，
因此答案即為： ∑ i = 0 y ( x i ) \displaystyle\sum_{i=0}^{y}\dbinom{x}{i} i=0∑y?(ix?)

NC16543 NC20824

話不多說，直接給處理這種組合數相乘的兩個公式：
∑ i = 0 n ( n i ) 2 = ( 2 n n ) \displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^2=\dbinom{2n}{n} i=0∑n?(in?)2=(n2n?)
證明思路：考慮 ( 1 + x ) 2 n (1+x)^{2n} (1+x)2n中 x n x^n xn的系數與 ( 1 + x ) n ? ( 1 + x ) n (1+x)^n*(1+x)^n (1+x)n?(1+x)n中 x n x^n xn的系數的計算方法，
∑ i = 0 k ( n i ) ? ( m k ? i ) = ( m + n k ) \displaystyle\sum_{i=0}^{k}\dbinom{n}{i}*\dbinom{m}{k-i}=\dbinom{m+n}{k} i=0∑k?(in?)?(k?im?)=(km+n?)
證明思路：上一個式子的擴展，
直接帶就完事了，

NC15077

卡特蘭數擴展：折線法，
這里只介紹這種方法的通式，
假如我要從 ( 0 , 0 ) (0,0) (0,0)走到 ( m + n , n ? m ) (m+n,n-m) (m+n,n?m)，其中， n n n步斜向上走， m m m步斜向下走，條件是不能走到 y y y軸以下的部分，
利用容斥原理，總的方案數是 ( n + m n ) \dbinom{n+m}{n} (nn+m?)，扣除掉不合法的情況，即為 ( 0 , ? 2 ) (0,-2) (0,?2)走到 ( m + n , n ? m ) (m+n,n-m) (m+n,n?m)，其中， n + 1 n+1 n+1步斜向上走， m m m步斜向下走的方案數，
因此合法方案數為： ( n + m n ) ? ( n + m n + 1 ) \dbinom{n+m}{n}-\dbinom{n+m}{n+1} (nn+m?)?(n+1n+m?)
這個方法在處理卡特蘭數相關問題有極大的用處，尤其是堆疊的壓入彈出操作的計數，

NC16537

先給出三個相關公式：
n n n條直線劃分平面，最多劃分出多少個部分？
n ( n + 1 ) / 2 + 1 n(n+1)/2 +1 n(n+1)/2+1
n n n個平面劃分空間，最多劃分出多少個部分？
( n 3 + 5 n + 6 ) / 6 (n^3+5n+6)/6 (n3+5n+6)/6
n n n條直線劃分空間，最多劃分出多少個部分？
( n ? ( n + 1 ) / 2 + 1 ) ? ( n 3 + 5 n + 6 ) / 6 (n*(n+1)/2+1) * (n^3+5n+6)/6 (n?(n+1)/2+1)?(n3+5n+6)/6
三個公式的證明方法都是直接遞推找增加的部分，
但很可惜的是，這三個公式對這道題沒有絲毫幫助，
考慮平面圖上的歐拉公式 n ? m + r = 2 n-m+r=2 n?m+r=2其中 n n n為頂點數， m m m為邊數， r r r為面數，
要求 r r r的值，
首先看頂點數，完全圖內每兩條對角線交出一個點，有 ( n 4 ) \dbinom{n}{4} (4n?)個，加上圓周上的 n n n個，
再看邊數，直接不好求，轉化為頂點的度數除以2，完全圖內的點的度數都是4，圓周上的點的度數都是 n + 1 n+1 n+1，總邊數為 2 ? ( n 4 ) + ( n ) ? ( n + 1 ) / 2 2*\dbinom{n}{4}+(n)*(n+1)/2 2?(4n?)+(n)?(n+1)/2
這樣 r r r的值就很好求了，

star 4

NC13229

完全二分圖的染色問題，不妨套路性地轉化為 n ? n n*n n?n的棋盤上的放棋子問題（其中每行每列最多只有一個棋子），
給出這種放棋子問題的公式： ∑ i = 0 n ( n i ) 2 ? i ! \displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^2*i! i=0∑n?(in?)2?i!
但這道題將其擴展到了兩種顏色，于是順理成章地想到方案數為 ( ∑ i = 0 n ( n i ) 2 ? i ! ) 2 ? {(\displaystyle\sum_{i=0}^{n}\dbinom{n}{i}^2*i!)}^2- (i=0∑n?(in?)2?i!)2?存在兩個不同顏色的棋子在同一個格子里的方案數，
考慮容斥：基本容斥思想為：總方案數-有一個棋子在同一個格子+有兩個棋子在同一個格子-有三個棋子在同一個格子……
接下來計算有 k k k個棋子在同一個格子的方案數，
讓 k k k個棋子選擇棋盤上的格子，然后把這 k k k行 k k k列摳掉，剩下一個 n ? k n-k n?k階的棋盤上隨便擺，就是 ( ∑ i = 0 n ? k ( n ? k i ) 2 ? i ! ) 2 {(\displaystyle\sum_{i=0}^{n-k}\dbinom{n-k}{i}^2*i!)}^2 (i=0∑n?k?(in?k?)2?i!)2，
因此最終的答案為： ∑ k = 1 n ( ? 1 ) k ? ( ∑ i = 0 n ? k ( n ? k i ) 2 ? i ! ) 2 ( n k ) 2 ? k ! \displaystyle\sum_{k=1}^{n}(-1)^k*{(\displaystyle\sum_{i=0}^{n-k}\dbinom{n-k}{i}^2*i!)}^2\dbinom{n}{k}^2*k! k=1∑n?(?1)k?(i=0∑n?k?(in?k?)2?i!)2(kn?)2?k!
但是這個演算法是 n 2 n^2 n2的，瓶頸在于求解 n ? n n*n n?n的棋盤上的放棋子問題是 O ( N ) O(N) O(N)的，
考慮遞推求解從 k k k階棋盤擴展道 k + 1 k+1 k+1階棋盤，
總方案數：在新增的 2 ? k + 1 2*k+1 2?k+1個格子上擺一個棋子，剩下 k k k階棋盤隨便擺，或者不多擺棋子，
矛盾方案：在除了右下角的格子外，在剩余的新增的 2 ? k 2*k 2?k個格子中擺棋子，并且該行或該列中已有棋子，剩下 k ? 1 k-1 k?1階棋盤隨便擺，
因此：
f [ k + 1 ] = 2 ? ( k + 1 ) ? f [ k ] ? k 2 ? f [ k ? 1 ] f[k+1]=2*(k+1)*f[k]-k^2*f[k-1] f[k+1]=2?(k+1)?f[k]?k2?f[k?1]
然后就能 O ( n ) O(n) O(n)求答案了，

NC20037

關于prufer序列的一些抄寫 學習筆記，
生成prufer序列：每次取編號最小的葉子節點，將父親加入序列中并洗掉該節點，直至剩下兩個節點，用堆可以輕松實作，
prufer序列轉為樹：每次取prufer序列的開頭和序列中最小的未出現的點連邊，
prufer序列的性質：

1. 長度為 n ? 2 n-2 n?2
2. p r u f e r prufer prufer序列與無根樹一一對應，
3. 度數為 d i d_i di?的節點會在pruferprufer序列中出現 d i ? 1 d_i-1 di??1次
4. 序列的所有情況可以得出 n n n階完全圖的生成樹的個數，即 n n ? 2 n^{n-2} nn?2
5. 由可重排列的計數可得，給定度數的樹的種類數為 ( n ? 2 ) ! / Π i = 1 n ( d i ? 1 ) (n-2)!/\displaystyle\Pi_{i=1}^{n}(d_i-1) (n?2)!/Πi=1n?(di??1)

于是，這道題的答案就呼之欲出了，

star 5