一開始我在那里dp推，發現有重復之類的東西不好搞
 看了Sevenkplus的，容斥，感覺好神奇
 
 最多有P = N - M + 1個回文串
 由于規模比較小，枚舉選出哪幾個作為回文串，使得至少有K個，令這個模式為Ti
 （如N = 3, M= 2 , K = 1 ，一個合法的模式為 010）
 則答案為|T0∪T1...∪Tc|，這里就要用到容斥了
 = ∑|Ti|
   -∑|Ti∩Tj|
   +∑|Ti∩Tj∩Tk|
   ...
     直接套用的話復雜度為2^(2^P) ??！

  與平常的容斥有點不一樣，這里存在很多“Tj包含于Ti”，即其交集就是子集了
  如011包含于010
  因為滿足011的肯定滿足010，所以011是010的子集，這里注意了??！二進制枚舉Ti的超集Tj，是模式Ti的子集

  畫個韋恩圖，一個集合Tj要計算的次數就是先減去其余集合Ti在這部分算的次數（減完就為空了），再加上1
  即為 1 - 其余集合Ti在這部分算的次數
 用num[i]表示集合Ti需要算的次數，則num[i] = 1 - ∑num[ii]  ii為i的超集
 for(int j = i+1 ; j < (1<<P) ; j++)
 {
  if((j & i) == i)//j是i的子集
   num[j] -= num[i];
 }
 所以集合Ti對答案的貢獻為 ans += num[i]*26^cnt
 O((2^p)^2)
 cnt為集合Ti獨立變量的個數
 對Ti,求獨立變量的個數，可以先建圖（利用回文串兩端相等的性質），然后dfs算出連通塊的個數就是獨立變量的個數了
*/


TCO'10 Qualification Round 1A 1000pt MegadiamondHunt
/*
 將只含有'<','>'的串，每次去掉<..<>..>連著的幾個
 如果去掉中有n對，則得分為n^2
 求最大得分
 
 一開始以為去掉的順序沒關系，過不了最后一個sample
 看了LayCurse的代碼，它是每次選擇 極大的<..<>..>中最小的一個去掉
 這樣子去貪心...
 如 <<<>><>>
 如果先去掉<<>>，然后剩下<<>> 得分為 2^2+2^2
 但若先去掉<>，則剩下<<<>>> 得分為 1 + 3^2
 因為，考慮一個極大的<..<>..>,若它能擴大，則它的左右肯定先去掉了一個
 極大的<..<>..>，如果已去掉的那個比當前的大，得分是不會比先去掉當前
 這個較小的大，所以每次選極大中的最小那個去掉
*/

zoj 3458
/*
 0 < b - a < 1 + 2sqrt(a)  求 floor(sqrt(a)+sqrt(b))^n % 2(a+b)

 看watashi的，沒接觸過這種問題，做法挺神奇( ⊙ o ⊙ )！

 由 0 < b - a < 1 + 2sqrt(a)
  => 0 < sqrt(b) - sqrt(a) < 1
 令Xn = (sqrt(b)+sqrt(a))^2n = (b+a+2sqrt(ab))^n
    Yn = (sqrt(b)-sqrt(a))^2n = (b+a-2sqrt(ab))^n
    Zn = Xn +Yn = (b+a+2sqrt(ab))^n + (b+a-2sqrt(ab))^n
 
 由于X1 = b+a+2sqrt(ab) , Y1 = b+a-2sqrt(ab)
 是方程(U-X1)(U-Y1) = 0 ，即 U^2 - 2(a+b)U + (a-b)^2 = 0 的根
 則Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
 用矩陣乘法可以求得Zn
 由于Yn<1 ，所以floor(Xn) = Zn - 1，所以最后答案Zn-1即可

 以上方法有個地方
 “
 由于X1 = b+a+2sqrt(ab) , Y1 = b+a-2sqrt(ab)
 是方程(U-X1)(U-Y1) = 0 ，即 U^2 - 2(a+b)U + (a-b)^2 = 0 的根
 則Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
 ”
 我不太懂，查了下特征根的一點東西
 若An+2 = pAn+1 +qAn
 則An = C1α^n + C2β^n
 上面應該是逆過來
 由Zn = Xn +Yn = (b+a+2sqrt(ab))^n + (b+a-2sqrt(ab))^n
 推出Zn+2 = 2(a+b)Zn+1 - (a-b)^2Zn
*/


zoj 3461
/*
 給出一個無向圖，有邊權，點權。點權val[i]為正的表示要將val[i]分出給點權為負的，每個點可以作為中間節點
 點權val[i]為負的表示要接收val[i]，傳送的花費為路徑的距離，求最小距離
 n<=16

 按照題意，花費即為∑val[i] = 0 的樹的MST 
 我有想過需要劃分成幾部分，起初沒想過怎么劃分

 解題報告是枚舉子集作為一部分樹，dp求解（n那么小，要往集合方面想吧?。?br> 即dp[mask] = dp[mask^i] + mst[i];
 注意需要sum[mask] = 0 的才有意義
*/


zoj 3463
/*
 一只手，相對拇指不動，至少要占5個鍵的位置，至多可以彈到9個鍵。
 拇指移動距離x需要花費floor(sqrt(x))，已知左右手初始位置和接下來
 需要彈奏的1000個鍵，求最小花費。

 狀態比較明顯，dp[n,l,r]表示已經彈了n個音符，左、右手拇指分別在l,r
 的最小代價
 無效狀態很多，不能計算，否則會超時
 枚舉左右手到需要彈的位置，其他情況不用考慮，不會更優

 這句話不太懂："But, one finger touching the key between two fingers of the other hand is fobidden."
 貌似不用處理？
 
 看watashi的代碼的
 sqrt的初始化很漂亮

 hdu 3651是簡化版，都是無效狀態不用算，決策是直接到需要的位置
*/


zoj 3464
/*
 N個人，起初在一條線上。
 每個人有速度vi，且每個人最多只能跑帶著棒Ts，問最快時間接棒跑完L

 貪心，最快的人跑最后Ts，倒數第二快的跑倒數第二Ts...
*/



TCO'10 Wildcard Round 500pt CalculationCards
/*
 n<=50張卡 如3張：+1 ,-2 , *3  其排列有
 0 + 1 - 2 * 3 = -5
 0 + 1 * 3 - 2 = 1
 0 - 2 + 1 * 3 = 1
 0 - 2 * 3 + 1 = -5
 0 * 3 + 1 - 2 = -1
 0 * 3 - 2 + 1 = -1
 期望為-1.6666666666666667
 求給定的n張卡的期望值

 不可能n!的枚舉
 設+、-卡共有s張
 按照一個+、-卡后接連續的*卡分類，則有s部分，其全排列不影響期望（總共s!種，但期望都一樣）
 所以只考慮無序的（無序可以用默認的一種順序，即卡出現的先后順序，或者說編號）
 ***a1***a2*** ... as***
 ***表示*卡
 由于是等概率的，所以總體來統計，每個+、-卡都會接同樣的*卡，
 既然每張+、-卡情況一樣，那就考慮a1卡
 其后會接0,1...,m張*卡
 答案就是 sum * (0,1,...m)張*卡的期望   sum = ∑ai
 求k張*卡的期望可以用dp做
 看bmerry代碼的做法，解題報告的麻煩一點吧
 一開始只有s張a卡排著，然后插入一張張*卡
 dp[i,j]表示插入了前面i張*卡，a1后接j張*卡，它們構成的期望值
 分第i張卡插不插入到a1之后構成j張連續的*卡，概率為 該插入的位置/總位置
 dp[i,j] =
    dp[i-1,j] * (n-j-1)/n
   + m[i]*dp[i-1,j-1] * j/n
 n為s+i

 這道題一個很好的想法就是答案為sum * (0,1,...m)張*卡的期望   sum = ∑ai   ！?。。。?！
 而求后接k張*卡的期望，bmerry的做法是一張一張卡插入，然后求得期望
 小規模到大規模，通過考慮插入位置來實現，這個做法應該較好
*/


TCO 2010 Qualification Round 1 250pt
/*
 題意：一個只有B,G組成的串，要將他們swap相鄰的，變成BB...GG或GG...BB
 求最少的次數  串長<=50
 我用n^2的求逆序對，太慢了
 看了別人的，直接就是累計將每個字母B移到左邊的步數
 if(row[i] == 'B')
 {
  tot += i - x;
  x ++;
 }
 x是當前需要放B的位置，交換后就++移到下個位置
*/



TCO'10 Qualification Round 2 1000pt HandlesSpelling
/*
 給出一個文本串，一些模式串
 現要將模式串覆蓋文本串，不能有重疊部分
 求使得A^2 - B 最大
 A是最長覆蓋的長度，B是還未覆蓋的個數

 一開始一直關注A^2 - B ，不知怎么做
 解題報告是分開來做
 要求得A^2 - B的最大值，可以通過枚舉A
 枚舉某一段作為最大覆蓋值，然后看其左右未覆蓋的個數

 而計算為覆蓋的個數可以通過dp了
 dp[i,j]表示[i,j]為覆蓋的個數
 枚舉[i,i']一段是被覆蓋的，則答案就是min(dp[i'+1,j])
 注意的是，初始化有些dp[i,j]=0，就直接continue
*/


SRM 216 Refactoring
/*
 問一個數n<=2*10^9 可以拆分成多少種因子相乘的情況
 24 = 2*2*2*3
   = 2*2*6
   = 2*3*4
   = 2*12
   = 3*8
   = 4*6
 
 不需要高深的數學知識?。。?br> 暴力dfs做
 f(n) = 1 + ∑f(n/i) 
 i 為其因子,i > 1 && i <= n/i（保證不會進入多余的分支）
 為了保證無序，可以多加一個參數start，表示該輪的因子>=start
*/



SRM 223 PrimeAnagrams
/*
 給出一個數字串len<=8
 求將其分為三部分，每部分都是素數，且乘積最小

 看解題報告的
 8! = 40320 ，而分成3部分情況為C(7,2) = 21種
 所以枚舉全排列，然后分成3部分來做

 Brute Force ！?。。。。?br>*/


zoj 3471 mask dp
/*
 n<=10個球，i碰j會產生a[i,j]的能量，j同時會消失
 問最多產生的能量之和
 
 我知道跟mask有關，為啥還是想不出？
 
 要從整體來看??！
 現在有一些球，掩碼為mask
 假設最先碰撞的是u->v，然后v消失了
 局面就變成了沒有v的一些球了, mask^(1<<v)，一個子問題了
 所以轉移就是枚舉u,v
 dp[mask] = max(dp[mask^(1<<v)+a[u][v]) 

 從局面來看吧?。?！

 一開始我是像zoj 3461 dp[mask] = dp[mask^i] + mst[i];
 發現會出問題，這樣子是隔離了一部分，但顯然隔離了后會丟失了連接著兩部分的那個值
 
*/

zoj 3470
/*
 如圖，問某個數字上下左右的數字是多少
 既然題目給了一副對應的坐標，發現，問題的重點就在于點坐標跟數字的轉換
 
 我是先找出數字val在第n圈 即 (n-1)^2 < val <= n^2
 然后該圈的起點start就是(n-1)^2 + 1 ， 然后通過比較start，就能求出坐標了
 發現奇數圈會使minx--,miny-- ; 偶數圈會使maxx++,maxy++
 數量關系是minx = miny = -(n-1)/2 , maxx = maxy = n/2
 
 然后點(x,y)轉化為值，跟上面類似的
 求出第n圈  二分判斷 minx<=x<=maxx , miny<=y<=maxy
 然后求出角落的點等等...
*/


zoj 3468
/*
 Dice游戲，一開始Attacker Defender各有骰子n,m個
 雙方拿出一定骰子來投，累計和
 誰多點誰贏
 Attacker拿出至少1個來攻擊
 問Attacker一次攻擊贏的概率
 骰子數目<=8
 枚舉Attacker投出的和為j，然后計算達到j的方法數，以及Defender投出的和小于j的方法數
 
 用背包的方法計算方法數
*/

CF 60D
/*
 n<=10^6個點，每個點有權值a[i]<=10^7 各不相同
 若存在一個數x，使得a[i],a[j],x   is a beautiful triple
 即a^2 + b^2 = c^2   a,b,c互素
 則i可以傳播laugh到j
 問最少需要需要讓多少個頂點自行laugh，然后傳播到全部的頂點

 看了解題報告的
 并查集做
 但如何判斷beautiful triple 兩兩判斷O(n^2)會超時

 有個性質：對于滿足a^2 + b^2 = c^2的數，可用勾股數公式生成：
 (x^2-y^2 , 2xy , x^2+y^2)  x>y
 該公式能生成所有的素勾股數（互質），需1奇1偶 ，且gcd(x,y) = 1
 也能生出部分派生勾股數(如 6 8 10) ， 2奇或2偶
 
 由于a[i]<=MAX       MAX= 10^7
 所以必有x^2-y^2 <= MAX , 2xy <= MAX  但x^2+y^2不一定<= MAX
 2y^2<=MAX
 x^2<=MAX+y^2<=3MAX/2
 => x<=sqrt(3MAX/2) , y <= sqrt(MAX/2)
 所以枚舉x,y復雜度為O(MAX)
 (注意x,y是1奇1偶且gcd(x,y) = 1)

 參考watashi代碼寫的 
*/


CF60E
/*
 一開始 n <= 10^6 個 Mushroom 按升序排成一條直線 ， 每個Mushroom重為a[i]
 下一秒時，a[i] , a[i+1] 之間會出現一個a[i]+a[i+1]的Mushroom
 而x秒時，某人重新排序這些Mushroom
 問再經過y秒，所有Mushroom的重量之和

 0 a1  a2  a3
 1 a1  a1+a2  a2  a2+a3  a3
 2 a1  2a1+a2  a1+a2  a1+2a2  a2  2a2+a3  a2+a3  a2+2a3  a3
 3 ...
 設時間i時重量為Ti 則Ti = 3Ti-1 - (a1+an)
 所以前x可用矩陣乘法求出Tx
 然后由于sort，最大的值是Fx-1*an-1 + Fx*an （找規律 Fx-1*ai-1 + Fx*ai , Fx*ai-1 + Fx-1*ai）
 F是斐波那契數列  F[-1] = 0 , F[0] = 1
 然后修改a1+an值即可，再次矩陣乘法 算出后來的y秒
*/


noip2002 G2 字串變換 雙向BFS
/*
 給出A,B串
 以及一些變化方法，即x->y
 求A變到B的最短步數
 
 bfs慢點
 雙向會快點
 由于x->y是單向的，所以兩邊的結構不同，優先擴展隊列長度短的優化就有用了
 注意反向BFS時擴展的順序是y->x
*/

poj 2411
/*
 問n*m的棋盤放置1*2的骨牌的方案數
 n,m<=11
 
 枚舉行，遞推計算列
 dp[row,col,s]  row行之前已經放好,且當前row行處于s狀態
 遞推 通過在row行，col列之后放置，擴展計算
 dp[row,col,s1] += dp[row-1,col,s2]

 不是記憶化搜索 是從0遞推
 為了打表，在每個分支都計算了  即:dp[row][col][s1] += dp[row-1][col][s2];
 否則，可以在最后的時候才計算的
*/

sgu 131
/*
 n*m棋盤，問用1*2, 2*2去掉一個角的骨牌覆蓋完的方案數
 
 狀態定義為 dp[row,s]表示當前第row行狀態為s，且前row-1行已經覆蓋完的方案數
 則 dp[row,s] <-- dp[row-1,s']
 轉移是枚舉row這一行每個位置（注意是整行）怎么放
 同時，若枚舉了row怎么放，則由狀態的定義，row-1之前的必須覆蓋完，就知道了s'是什么了！！！
 
 每個位置有7種放法，除了被之前的方法限制了，就不足
*/


hdu 2640
/*
 n*m的棋盤，有一些位置不能放，問最多能放多少個十字架
    @
 @@@
    @

 注意的是，每個@都需要放，所以棋盤相應的位置需要是空的
*/


xmu 1118
/*
 求用1*1,1*2,1*3的磚塊鋪滿 3*N的板的方案數目
 1*3，最多影響3行 所以狀態需要記錄當前行以及前一行的情況  2bit 共4種
 _    *    _    *
 _    _    *    *
 _表示空，*表示被覆蓋

 dp[row,s]表示row-1之前的已經覆蓋完了，row-1,row的狀態為s時的值
 
 對row這一行的每個位置，枚舉其放的方法
 雖然說4種狀態，實際上轉移時很多是不需要的。因為為了滿足row-1之前的是覆蓋完的

不放，可以轉移兩種，即上面的1,2種類型
*/



hdu 2240
/*
 給出如圖n*5棋盤，其中第一塊最多只能用c個，其余的不限
 問能否鋪滿
 跟sgu 131類似
 不過這里dp的值是記錄最少使用的1
 b1,b2是之前的方法對當前的影響
*/



hdu 2606
/*
 用1*1, 2*2, 3*3, 4*4覆蓋完N*4的棋盤的方案總數
 遞推
 dp[n] =  dp[n-1]         最底部放4個1*1
           + 4*dp[n-2]     最底部組合出2*4的，總共有4種
           + 4*dp[n-3]     最底部組合出3*4的，總共有4種  2個是2塊2*2上下交錯 2個是一塊3*3
           + 3*dp[n-4]     最底部組合出4*4的，總共有3種  2個是3塊2*2上下交錯 1個是一塊4*4
    + 2*(dp[n-5]+dp[n-6]...+dp[0])    用2*2上下交錯放的
 則dp[n-1] = ....
 兩式相減，得到dp[n] = 2dp[n-1] +3dp[n-2] - dp[n-4] - dp[n-5]    n>=5
 至于n<=4的，結合上面的dp[n]的式子計算

 腦殘了，wa了好幾次
 沒想到可以2*2上下交錯  腦殘
*/



hnu 10816 ugly number
/*
 題意：給出n個素數<=10000  n<=10
 問[x,y]區間內只包含這些素數因子的數，要求全部打印出來
 x,y<=2^31
 一開始看到規模嚇了一跳
 事實上，只含有這些因子的數是很少的
 注意不是倍數?。≈暗谝挥∠罂闯杀稊?，搞個容斥了，算了下2和3的，數據巨大....
 
 像poj 的 ugly number那樣子做
 由于每個數都得乘以這些素數來擴展
 用num[]數組存儲生成的所有數
 pos[i]表示素數pr[i]當前要乘以num[pos[i]]
 初始num[0] = 1  pos[i] = 0
 然后每一步擴展一個數，該數為num[tot] = min(num[pos[i]]*pr[i])
 然后判斷每個num[pos[i]]*pr[i] 是否 = num[tot]，是的話 pos[i]+1
 
 這種思想還是沒能很好掌握...
 肯定的是，每個數都得乘以pr[1],pr[2]...
 要用pos[i]記錄當前pr[i]乘到哪個數了！?。?br>*/



08 ZhuHai Contest  E Magic Squares 雙向bf
/*
 問一個排列變為3*3幻方的最小步數
 每一步可以選擇一個角進行旋轉
 
 狀態數不多9!
 先全排列得到目標狀態
 再雙向bfs  挺快的
 用康托展開（變進制）判重更快
*/


poj 3255 無向圖值次短路 ★★★
/*
 給出一個無向圖 n<=5000, m <= 30000
 求1到n的值次短的路，如果有多條最短路，但次短的還是需要大于最短的
 允許點、邊走多次

 靠解題報告保養~~~ T_T
 求1到其他點的最短路dist[] ，再求n到其他點的最短路rdist[]
 枚舉每條邊，找到次短的 dist[u] + (u,v) + rdist[v]

 啟示:  枚舉哪條邊作為中間的必須經過的邊u->v，然后連接1->u, v->n
*/


scu 3904
/*
 一個序列seq[i]   n<=10^5                -10000<=seq[i]<=10000
 將其劃分成幾部分，使得每一部分之和>=0
 求所有的劃分方法數
 顯然dp[i] = ∑dp[j]   (sum[i] - sum[j] >= 0)
 O(n^2)會超時
 用線段樹加速
 我一開始是以下標作為線段樹的數軸，記錄該段Min[p],Max[p],還有一個sDp[p]記錄該段所有dp值
 但這樣比較慢，維護相對多了點

 看了標程，是先計算所有的sum[]，然后離散化
 以sum值作為數軸來搞，用樹狀數組就很容易寫了

*/


中大第三本 ch2 負權數
/*
 平時 N = anR^n + ... + a0R^0  其中R>0
 負權數是R < 0,使用負權數表示的優點是對于負數，不用前置的符號
 比如 -15 = 1*(-2)^5 + 1*(-2)^4 + 0*(-2)^3 + 0*(-2)^2 + 0*(-2)^1 + 1*(-2)^0
 現給出N,  -16<= R <=-2
 求N的負權數R表示（題目的答案輸出一行，表明表示是唯一的）
 (無論正權、負權，系數ai都是 0<=ai<|R|)
 
 因為取余運算只使用語正整數除法，所以不能通過連續連除求余的方法?。。?！
 寫成普通形式時：

 N >= 0
 N = an|R|^n + ... + a0|R|^0 R < 0
 i為奇數時:
  ai|R|i = R(i+1) + (|R|-ai)Ri          為了保證a'>=0
 i為偶數
  ai|R|i = aiRi
 所以先將N寫成正權形式，然后再修改為負權的

 同理
 N < 0
 N = -(an|R|^n + ... + a0|R|^0) R < 0
 i為奇數時:
   -ai|R|i = aiRi         為了保證a'>=0
 i為偶數
  -ai|R|i = R(i+1) + (|R|-ai)Ri

 最后對a'[]進行修正，使得0 <= a'i < |R|

 感覺挺不錯的一道題，通過對正權的形式，修正為負權的
*/