最近TCOだGCJだでSRMのMediumつぶしがおろそかだったので。
http://community.topcoder.com/stat?c=problem_statement&pm=11888
問題
文字列W,A,Dが与えられる。
文字列xに対し、f(x)= W+x+A+x+D で定義できる。
ここでさらに文字列S,Fと整数kが与えられる。
f^k(S)中、部分文字列としてFは何回登場するか答えよ。
解法
まず、f(x)の長さがF以上になるまでは適当に何回か関数fを適用しておくと後の処理が楽である。
以下のコードでは、100文字を超えるまではfを繰り返した。
f^i(x)について、Fの登場回数及び先頭100文字(prefix)と末尾100文字(postfix)を覚えておき、DPしていく。
この時、f^(i+1)(x)におけるFの登場回数は、f^i(x)における登場回数の2倍に、W+prefix、postfix+A+prefix、prefix+Dの各文字列に登場するFの回数を加えたものである。
よって順々にiを増やしながらf^i(x)におけるFの回数を数えることができる。
ただ、この問題はkの上限が10^7とかなり大きいため、文字列検索をしながらiをインクリメントするとTLEする。
一方、iが100を超えるとprefixはWを繰り返したもの、postfixはDを繰り返したものになるので、W+prefix、postfix+A+prefix、prefix+DにおけるFの登場回数は常に同じになる。
この登場回数をaddとすると、f^(i+1)(x)のFの登場回数はf^i(x)*2+addと簡単な式で書けるようになり、10^7回繰り返してもTLEしなくなる。
ll mo=1000000007; class AkariDaisukiDiv1 { public: int dp[2][51]; int countF(string W, string A, string D, string S, string F, int k) { int i,j; ll ret=0,add; while(S.size()<=100 && k) S=W+S+A+S+D, k--; FOR(i,(int)S.size()-(int)F.size()+1) ret+=S.substr(i,F.size())==F; if(k<=0) return (int) ret; string s1=S,s2=S; FOR(i,F.size()+5) { if(k--<=0) return (int) ret; s1=s1.substr(0,100); s2=s2.substr(s2.size()-100); add=0; string ss=s2+A+s1; s1=W+s1; s2=s2+D; FOR(j,W.size()) add+=F==s1.substr(j,F.size()); for(j=100-F.size()+1;j<100+A.size();j++) add+=F==ss.substr(j,F.size()); FOR(j,D.size()) add+=F==s2.substr(s2.size()-F.size()-j,F.size()); s1=s1.substr(0,100); s2=s2.substr(s2.size()-100); ret = (ret*2+add) % mo; } while(k-->0) ret=(ret*2+add) % mo; return (int)ret; } }
まとめ
結局f^i(x)の先頭と末尾はある程度以降は同じになる点がポイント。
これはすんなり自力で解けた。