Codeforces ECR #039 : F. Fibonacci String Subsequences

これも方針はあんまり迷わなかったな。
http://codeforces.com/contest/946/problem/F

問題

文字列を返す関数F(x)を以下のように定める。

• F(0) = "0"
• F(1) = "1"
• F(i) = F(i-1) + F(i-2) (i＞1)

整数xと01で構成された文字列Sが与えられる。
F(x)において(不連続でもよい)部分文字列としてSが何回登場するか。

解法

S	がたかだか100である点に注目しよう。

行列累乗で解く。
文字列F(x)の部分列を考える前の段階で|S|のうちi文字までマッチした状態のとき、F(x)の全部分文字列2^|F(x)|通りを考えたとき、どこまでマッチしたものが何通りできるか、および最後までマッチするケースが何通りできるか、とそれぞれ２つの行列を作ればよい。

int N,X;
string S;
int nex[102][2];
int add[102][2];

ll pat[101][101][101];
ll padd[101][101][101];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>X>>S;
	
	FOR(i,N) {
		FOR(j,2) {
			if(S[i]=='0'+j) {
				nex[i][j]=i+1;
				if(i+1!=N) continue;
				add[i][j]=1;
			}
			string T=S.substr(0,i)+(char)('0'+j);
			for(x=i;x>=0;x--) {
				if(T.substr(T.size()-x)==S.substr(0,x)) {
					nex[i][j]=x;
					break;
				}
			}
		}
	}
	
	FOR(i,N) {
		// F[0]
		pat[0][i][i]++;
		pat[0][i][nex[i][0]]++;
		padd[0][i][nex[i][0]]+=add[i][0];
		// F[1]
		pat[1][i][i]++;
		pat[1][i][nex[i][1]]++;
		padd[1][i][nex[i][1]]+=add[i][1];
	}
	for(i=2;i<=X;i++) {
		FOR(x,N) FOR(y,N) FOR(z,N) {
			(pat[i][x][z]+=pat[i-1][x][y]*pat[i-2][y][z])%=mo;
			(padd[i][x][z]+=pat[i-1][x][y]*padd[i-2][y][z]+padd[i-1][x][y]*pat[i-2][y][z])%=mo;
		}
	}
	ll ret=0;
	FOR(j,N) ret+=padd[X][0][j];
	cout<<ret%mo<<endl;
	
	
}

まとめ

こういうフィボナッチ数列風の問題は大体再帰的に解けるな。