const int MAXN = 1100000; int dp[MAXN][2][2]; char ipt[MAXN]; int len; void fun() { dp[0][0][0] = dp[0][0][1] = 1; FE(i, 1, len) { if (ipt[i] == ‘?‘) { //0 dp[i][0][0] += dp[i - 1][0][0]; dp[i][0][0] %= MOD; //1 dp[i][0][1] += dp[i - 1][0][0]; dp[i][0][1] %= MOD; dp[i][0][0] += dp[i - 1][1][0]; dp[i][0][0] %= MOD; //2 dp[i][0][1] += dp[i - 1][1][0]; dp[i][0][1] %= MOD; //* dp[i][1][0] += dp[i - 1][0][1]; dp[i][1][0] %= MOD; dp[i][1][1] += dp[i - 1][0][1]; dp[i][1][1] %= MOD; dp[i][1][0] += dp[i - 1][1][1]; dp[i][1][0] %= MOD; dp[i][1][1] += dp[i - 1][1][1]; dp[i][1][1] %= MOD; } else { switch (ipt[i]) { case ‘0‘: dp[i][0][0] += dp[i - 1][0][0]; dp[i][0][0] %= MOD; break; case ‘1‘: dp[i][0][0] += dp[i - 1][1][0]; dp[i][0][0] %= MOD; dp[i][0][1] += dp[i - 1][0][0]; dp[i][0][1] %= MOD; break; case ‘2‘: dp[i][0][1] += dp[i - 1][1][0]; dp[i][0][1] %= MOD; break; case ‘*‘: dp[i][1][0] += dp[i - 1][0][1]; dp[i][1][0] %= MOD; dp[i][1][0] += dp[i - 1][1][1]; dp[i][1][0] %= MOD; dp[i][1][1] += dp[i - 1][0][1]; dp[i][1][1] %= MOD; dp[i][1][1] += dp[i - 1][1][1]; dp[i][1][1] %= MOD; break; } } } } int main() { // freopen("in.txt", "r", stdin); while (~RS(ipt + 1)) { CLR(dp, 0); len = strlen(ipt + 1); fun(); cout << (dp[len][0][0] + dp[len][1][0]) % MOD << endl; } return 0; }
const int MAXN = 1100000; int ans[MAXN][2][2]; char ipt[MAXN]; int len; int fun(int ind, bool isPreStar, bool isCurStar) { if (ans[ind][isPreStar][isCurStar] != INF) return ans[ind][isPreStar][isCurStar]; int ret = 0; if (ind >= len) { if (!isCurStar) ret = 1; return ans[ind][isPreStar][isCurStar] = ret; } if (ipt[ind] == ‘?‘) { if (isPreStar) { if (isCurStar) { ret += fun(ind + 1, true, false); ret %= MOD; ret += fun(ind + 1, true, true); ret %= MOD; } else { ret += fun(ind + 1, false, false); ret %= MOD; ret += fun(ind + 1, false, true); ret %= MOD; } } else { if (isCurStar) { ret += fun(ind + 1, true, true); ret %= MOD; ret += fun(ind + 1, true, false); ret %= MOD; } else { ret += fun(ind + 1, false, false); ret %= MOD; ret += fun(ind + 1, false, true); ret %= MOD; } } } else { if (isPreStar) { if (isCurStar) { if (ipt[ind] == ‘*‘) { ret += fun(ind + 1, true, false); ret %= MOD; ret += fun(ind + 1, true, true); ret %= MOD; } } else { switch (ipt[ind]) { case ‘1‘: ret += fun(ind + 1, false, false); ret %= MOD; break; case ‘2‘: ret += fun(ind + 1, false, true); ret %= MOD; break; } } } else { if (isCurStar) { if (ipt[ind] == ‘*‘) { ret += fun(ind + 1, true, true); ret %= MOD; ret += fun(ind + 1, true, false); ret %= MOD; } } else { switch (ipt[ind]) { case ‘0‘: ret += fun(ind + 1, false, false); ret %= MOD; break; case ‘1‘: ret += fun(ind + 1, false, true); ret %= MOD; break; } } } } return ans[ind][isPreStar][isCurStar] = ret; } int main() { // freopen("in.txt", "r", stdin); while (~RS(ipt)) { CLR(ans, INF); len = strlen(ipt); int ans = 0; ans += fun(0, false, false); ans %= MOD; ans += fun(0, false, true); ans %= MOD; cout << ans << endl; } return 0; }
原文:http://blog.csdn.net/wty__/article/details/21641195