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

star 5