Codeforces #508 Div2 F. Wrap Around

あれ、Editorialよりもすっきりできてる？
http://codeforces.com/contest/1038/problem/F

問題

N文字のバイナリ文字列Sのうち、ローテートしてM文字のバイナリ文字列Tを含むことになるものは何通りか。

解法

ローテートに関する問題の定番テクとして、初期状態を総当たりで仮置きし、1周処理し終わったときに同じ状態に戻りかつTを含むケースを数え上げることとする。
問題は何を状態と置くかだが、KMP法のマッチ文字数を状態と置くとよい。

KMP法の遷移テーブルを作っておき、仮置きした状態から初めて、各位置0/1が来た場合の遷移先のパターンをDPで求めていく。
途中T全部とマッチしたケースがあるかどうかを覚えておきつつ、最終的に元の状態に戻れるか確認しよう。

初期状態がN通り、各文字位置N通り毎に状態を|T|通り管理するのでO(N^2*M)で済む。

int N,M;
string S;
int nex[42][2];
ll dp[42][42][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	M=S.size();
	
	FOR(i,M+1) {
		FOR(j,2) {
			string T=S.substr(0,i)+(char)('0'+j);
			for(x=i+1;x>=0;x--) {
				if(S.substr(0,x)==T.substr(T.size()-x)) {
					nex[i][j]=x;
					break;
				}
			}
		}
	}
	
	ll ret=0;
	for(int state=0;state<=M;state++) {
		ZERO(dp);
		dp[0][state][state==M]=1;
		FOR(i,N) {
			FOR(x,M+1) {
				dp[i+1][nex[x][0]][nex[x][0]==M] += dp[i][x][0];
				dp[i+1][nex[x][0]][1] += dp[i][x][1];
				dp[i+1][nex[x][1]][nex[x][1]==M] += dp[i][x][0];
				dp[i+1][nex[x][1]][1] += dp[i][x][1];
			}
		}
		ret+=dp[N][state][1];
	}
	cout<<ret<<endl;
	
	
}

まとめ

最初Editorialの真似してO(N^2*M^2)かかるコード書いてしまった。