AGC022 E - Median Replace
? 解题记录 ? ? Atcoder ? ? 动态规划 ? ? 构造 ?    2018-07-15 11:00:04    752    0    0

### 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
times so that the only character of the resulting string is `1` :

• Choose three consecutive bits of X and replace them by their median. For example, we can turn `00110` into `010` by 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``1` or `?`.

### 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.

Copy
`1??00`

### Sample Output 1

Copy
`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 get `110` and then on the only 3 bits to get `1`.

• `11000` : This string is beautiful because we can first perform the operation on the last 3 bits to get `110` and then on the only 3 bits to get `1`.

• `10100` : This string is not beautiful because there is no sequence of operations such that the final string is `1`.

• `10000` : This string is not beautiful because there is no sequence of operations such that the final string is `1`.

Thus, there are 2 ways to form a beautiful string.

Copy
`?`

### Sample Output 2

Copy
`1`

In this case, `1` is the only beautiful string.

### Sample Input 3

Copy
`?0101???10???00?1???????????????0????????????1????0`

### Sample Output 3

Copy
`402589311`

## 然后变成了一个自创自动机上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;
}```

752 人读过

0 条评论