http://acm.scs.bupt.cn/onlinejudge/showproblem.php?problem_id=1586
題意:
一共有K(K<=50)種字母,組成一個長度為L(L<=10^18)的串.
這個串需滿足要求:
對任意的 1<=i<=L , 以及任意的 1<=k1,k2<=K 且 k1!=k2, 在前綴 s[1..i]中,字母k1的個數和字母k2的個數之差的絕對值<=2.
例如: abac是合法的; 而abbbc不合法, 因為前綴abbb中字母b和c的個數相差為3.
建立狀態:
從<=2 入手找狀態. 可以設前c個字母中, 最小個數為m, 字母數為m的種類為i, m+1的種類為j, m+2的種類為k. 化簡狀態可得 比最小個數多1的種類為i,比最小個數多2的種類為j. 而經過數學推導(不懂), 可知 j+2k<K, 也就是當 c%K 已知時, 可直接由k確定i和j. 這樣狀態數為 50*50=2500, 還是不能用矩陣法. 進一步思考, 由c%K=0時的結果可以推出c%K=1時的結果,遞推可把c%K=0...K-1的結果都求出. 而要求L步的結果數,實際上并不用去管是1步1步走,還是2步2步走. 所以我們可以直接一次走K步! 這樣就把c%K這一維狀態也消除了.
于是可以設矩陣m[i,j]為c%K=0時,k經過K步從i轉移到j的方法數.
這樣先求出 L-L%K 步的方法數, 最后 L%K 步直接dp即可.
整體復雜度為 K^3*log(L/K).

本題關鍵: 由k和c%K唯一確定i和j; 一次走K步, 消除狀態c%K, 實際上不同c%K對應的狀態是冗余的, 因為不用去管中間的過程.