SRM 648 250pt AB
題意：給出長度N，K，問存在多少個由AB兩個字元組成的字元串，滿足存在K對(i,j) (i < j)，且s[i] = 'A', s[j] = 'B'(N <= 50, K <= N * (N - 1) / 2)
思路：dp[i][j][k]表示當長度為i的時候，存在了j對，且前面有k個A，
那麼下一個字元，如果是A，則dp[i + 1][j][k + 1] += dp[i][j][k]，否則，如果是B，則(A,B)關系對增加了k個，dp[i + 1][j + k][k] += dp[i][j]][k]
| |
SRM 648 550 pt KitayutaMart
題意：給出N，K，有N種物品，第i種初始價格是i，每種都有無數次，對于同一種物品，每買一次，價格變成原來的兩倍，比如對第i個物品，第j次買的時候價格是i * 2^(j - 1)，問在最優情況下，買K個物品的價格是多少？(1 <= N,K <= 10^9)
思路：當第一次選N的時候，N / 2的肯定要多選一次，同理N / 4是N / 2的倍數等等 fun(n) = n + fun(n / 2)
枚舉最後一個選了P次，然後P * fun(n)，但是這樣可能數目不夠，對于多餘的，二分哪個物品取多了一次，也就是将新的n設定為二分的值，看看數量是否足夠即可。
| |
SRM 648 850pt Fragile
題意：給出N,K (N <= 50,K <= N - 1)，問存在多少個N個點無向圖，沒有自環，其橋的數目是K。 所謂橋，即斷開這條邊，不連通的塊增加
思路：用了比較麻煩的方法。需要預先解決幾個子問題。
（1）N個點的不同連通圖數目是多少（POJ 1737）。
N個點的邊數是N * (N - 1) / 2，是以任意選一些邊集的話，有TOT(N) = 2^(N * (N - 1) / 2)種情況。但是這樣包含了不連通的，需要減掉。
不連通的數量可以枚舉有多少個點與最小标号的1點連通，這樣就是sigma( C(nN- 1,i - 1) * i個點的連通圖 * TOT(N - i))，這個意思是，從N - 1個點中選出i - 1個點與1号點組成一個大小為i的連通圖，然後剩餘的N - i個點随便組，隻要不與1所在的連通塊連通即可
（2）N個點組成K個連通塊的方案數
有了（1），其餘就是一個普通背包，類似原理，枚舉目前點集最小标号的點的連通塊大小即可
（3）N個點組成一個無橋的連通圖方案數，即雙連通圖
N個點組成的連通圖方案數 - sigma(i個點組成雙連通圖方案數 * sigma(i個點的連通塊外面連了K個橋邊)）
sigma(i個點組成的雙連通圖方案數 * sigma(i個點的連通塊外面連了K個橋邊))，意思是最小标号1所在的雙連通塊的大小。由于N個點的圖是連通圖，是以1所在的雙連通塊必然與剩下的點連通，枚舉橋邊數目，然後是用N - i個點分成K個連通塊的數量，(2)已經求出
（4） N個點，分成C個不連通的塊，每個塊的橋總數為K
枚舉最小标号點1所在的塊大小i，已經橋的邊數x，然後 * (N - i 個點，組成C - 1個不連通的塊，每個塊的橋之和為K - x)
（5）N個點，組成剛好M個橋的連通圖方案數
（4）（5）是嵌套記憶化搜尋的。
枚舉1所在的雙連通塊的大小i，且這個塊去掉後分成了K個連通塊，那麼問題就是C(N - 1,i - 1) * (i個點組成一個無橋連通圖（3）) * (N - i個點，分成K個不連通的塊，塊的橋總和是M - K（4）)的方案數
（6）問題的最終解，即N個點的無向圖，具有K個橋的方案數
枚舉1所在的塊的點數i，橋數j，那麼就是 C(N - 1,i - 1） * i個點，j個橋的連通圖(5) * N - i個點的無向圖具有K個塊的方案數（6）（記憶化遞歸解）