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

本題關(guān)鍵: 由k和c%K唯一確定i和j; 一次走K步, 消除狀態(tài)c%K, 實(shí)際上不同c%K對應(yīng)的狀態(tài)是冗余的, 因?yàn)椴挥萌ス苤虚g的過程.