rockdu
Problem Statement
Taichi thinks a binary string X of odd length N is beautiful if it is possible to apply the following operation
| N−1 |
| 2 |
1 :
- Choose three consecutive bits of X and replace them by their median. For example, we can turn
00110into010by applying the operation to the middle three bits.
Taichi has a string S consisting of characters 0, 1 and ?. Taichi wants to know the number of ways to replace the question marks with 1 or 0 so that the resulting string is beautiful, modulo 109+7.
Constraints
- 1≤|S|≤300000
- |S| is odd.
- All characters of S are either
0,1or?.
Input
Input is given from Standard Input in the following format:
S
Output
Print the number of ways to replace the question marks so that the resulting string is beautiful, modulo 109+7.
Sample Input 1
1??00
Sample Output 1
2
There are 4 ways to replace the question marks with 0 or 1 :
11100: This string is beautiful because we can first perform the operation on the last 3 bits to get110and then on the only 3 bits to get1.11000: This string is beautiful because we can first perform the operation on the last 3 bits to get110and then on the only 3 bits to get1.10100: This string is not beautiful because there is no sequence of operations such that the final string is1.10000: This string is not beautiful because there is no sequence of operations such that the final string is1.
Thus, there are 2 ways to form a beautiful string.
Sample Input 2
?
Sample Output 2
1
In this case, 1 is the only beautiful string.
Sample Input 3
?0101???10???00?1???????????????0????????????1????0
Sample Output 3
402589311
Remember to output your answer modulo 10^9+7.
题目大意：给你一个0，1，？构成字符串。？可以是0或1。如果你可以通过以下操作把它变为1的话称这个字符串是好的：
选择连续的三个字符，把它们替换成出现次数最多的那个。
现在问，把？替换成0，1后的结果中，好的字符串有多少个。
这个题的脑洞实在是太神奇了……
我们自己发明一个自动机，让它可以识别出好的字符串：
注意第四层的单个节点，如果不加入这个节点的话"10001"这样的字符串就会被忽视，因为它可以把中间三个"0"缩起来，然后再操作一次就变为了"1"。
然后变成了一个自创自动机上DP了……
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 3e5 + 5, mod = 1e9 + 7;
int trans[][2] = {
{2, 1}, {4, 3}, {6, 5}, {3, 3}, {7, 1}, {2, 1}, {2, 2}, {4, 4}
};
int dp[maxn][10], n;
char rs[maxn], *s;
int main() {
scanf("%s", rs), n = strlen(rs), s = rs - 1, dp[0][0] = 1;
for(register int i = 0; i < n; ++i) {
for(register int j = 0; j < 8; ++j) {
if(s[i + 1] != '0')
(dp[i + 1][trans[j][1]] += dp[i][j]) %= mod;
if(s[i + 1] != '1')
(dp[i + 1][trans[j][0]] += dp[i][j]) %= mod;
}
}
printf("%d", (dp[n][1] + dp[n][3]) % mod);
return 0;
}
没有帐号? 立即注册