Typical DP Contest Q - 連結

問題

0, 1からなるn個の文字列wiが与えられる。
wiを並べて書いた文字列で、長さがLであるものはいくつあるか。
出来る文字列が同じならば、wiの並べ方は区別しないものとする。

制約条件

答えはmod 10^9 + 7で求める
n≦510

wi

≦8

L≦100

方針

dp[長さ][最後の7文字][区切りになれる場所] := 場合の数
を1文字ずつ更新するようなDP.

区切りになれる場所の遷移は、
前に区切れる場所で区切った後、残りが単語になっていれば、
今の長さの最後でも区切れる。

ソースコード

const int mod = inf + 7;
int n, l;
int dp[110][1 << 7][1 << 8];
bool word[10][1 << 8];

int main(){
	
	cin >> n >> l;
	rep(i, n){
		int bit = 0;
		string s;
		cin >> s;
		rep(j, s.size()) if(s[j] == '1') bit |= 1 << j;
		word[s.size()][bit] = 1;
	}
	
	dp[0][0][1 << 7] = 1;
	rep(i, l) rep(j, 1 << 7) rep(k, 1 << 8) rep(d, 2){
		
		int nj = j | d << 7;
		int nk = k >> 1;
		rep(m, 8) if(k & 1 << m) if(word[8 - m][nj >> m]) nk |= 1 << 7;
		
		(dp[i + 1][nj >> 1][nk] += dp[i][j][k]) %= mod;
	}
	ll ans = 0;
	rep(i, 1 << 7) rep(j, 1 << 8) if(j & 1 << 7) ans += dp[l][i][j];
	cout << ans % mod << endl;
	
	return 0;
}