dwangoプログラミングコンテスト A - ニコニコ文字列2
解法
dp[n][x][renzoku][f2] = (n 文字目の時点でニコニコ文字列が x 個あり, 25 という文字列が直前に renzoku 個続いていて, 直前の文字が 2 であるかどうかのフラグが f2 である場合に, 全体としてニコニコ文字列が X 個未満になるような場合の数)
という dp を求めます。文字列 S の ? 部分にはそれぞれ 10 通りの自由度があるので, 求める答えは ? の数 p に対して 10^p - dp[0][0][0][0] となります。dp は上手いことがんばりましょう。
下のコードではメモ化再帰していますが, dp を long long にすると MLE するなどあまりよろしくないので普通に for 文で dp したほうが良さそうです。
const int MOD = 1e9+7; const int MAXN = 255; int dp[MAXN][MAXN][MAXN][2]; int N, X; string S; int dfs(int n, int x, int renzoku, int f2) { if (x >= X) return 0; if (n >= N) return 1; int& ret = dp[n][x][renzoku][f2]; if (ret >= 0) return ret; ret = 0; if (isdigit(S[n])) { if (S[n] == '2') { if (f2) { ret += dfs(n+1, x, 0, 1); } else { ret += dfs(n+1, x, renzoku, 1); } ret %= MOD; } else if (S[n] == '5') { if (f2) { ret += dfs(n+1, x+renzoku+1, renzoku+1, 0); } else { ret += dfs(n+1, x, 0, 0); } ret %= MOD; } else { ret += dfs(n+1, x, 0, 0); ret %= MOD; } } else { for (int i = 0; i < 10; i++) { if (i == 2) { if (f2) { ret += dfs(n+1, x, 0, 1); } else { ret += dfs(n+1, x, renzoku, 1); } ret %= MOD; } else if (i == 5) { if (f2) { ret += dfs(n+1, x+renzoku+1, renzoku+1, 0); } else { ret += dfs(n+1, x, 0, 0); } ret %= MOD; } else { ret += dfs(n+1, x, 0, 0); ret %= MOD; } } } return ret; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> X; cin >> S; ll ans = 1; for (int i = 0; i < N; i++) if (S[i] == '?') (ans *= 10) %= MOD; memset(dp, -1, sizeof(dp)); ans = (ans+MOD-dfs(0, 0, 0, 0))%MOD; cout << ans << endl; return 0; }