5477: B-Fall with Soldiers
内存限制：512 MB
时间限制：12.000 S
评测方式：文本比较
命题人：
提交：6
解决：2
题目描述
Fall is playing a game about a war.
There are n soldiers standing in a line. Some of them belong to the player, while
others belong to the enemy. Due to the spies, the belonging of some of
them is unknown. Now, as an artillery, the player may win this game
under the following rules after identifying the belonging of each
soldier:
Step 1: Choose a soldier which belongs to the player.
There should be exactly two soldiers next to the chosen one, which means
the chosen soldier should be neither at the beginning nor at the end of
the line.
Step 2: Kill the soldiers next to the chosen one (the chosen one will remain alive).
Step 3: Repeat step 1 and step 2 until all the soldiers left belong to the same side (the player or the enemy).
The player wins if all the soldiers left belong to the player. Fall, as the
player, wants to know the number of ways to identify the belonging of
each soldier so that he can win.
However, soldiers may change their state (the player's troops, the enemies, or unknown). You need to
calculate the answers after every change.
There are n soldiers standing in a line. Some of them belong to the pla
Step 1: Choose a soldier which belongs to the pla
Step 2: Kill the soldiers next to the chosen one (the chosen one will remain alive).
Step 3: Repeat step 1 and step 2 until all the soldiers left belong to the same side (the pla
The pla
However, soldiers may change their state (the pla
输入
The input consists of multiple test cases.
The first line contains an integer T (1≤T≤11) -- the number of test cases.
For each test case:
In the first line, there are two integer n,q (1≤n,q≤2×105, n is odd), which are the number of soldiers and the number of operations.
In the second line, there is a string s of length n, which represents the initial soldier state. If si is '1', the soldier belongs to you. If si is '0', the soldier belongs to your enemy. If si is '?', the belonging of this soldier is unknown.
In the next q lines, each contains an integer p (1≤p≤|s|) and a charactor c, which means change sp to c.
It is guaranteed that the sum of q over all test cases will not exceed 106, si,c∈{′0′,′1′,′?′}
The first line contains an integer T (1≤T≤11) -- the number of test cases.
For each test case:
In the first line, there are two integer n,q (1≤n,q≤2×105, n is odd), which are the number of soldiers and the number of operations.
In the second line, there is a string s of length n, which represents the initial soldier state. If si is '1', the soldier belongs to you. If si is '0', the soldier belongs to your enemy. If si is '?', the belonging of this soldier is unknown.
In the next q lines, each contains an integer p (1≤p≤|s|) and a charactor c, which means change sp to c.
It is guaranteed that the sum of q over all test cases will not exceed 106, si,c∈{′0′,′1′,′?′}
输出
For each test case, output the initial answer in a single line. Then output q answers in q lines, which are your answers after each change. All the answers should be output modulo 109+7.
样例输入 复制
6
5 1
01000
1 1
5 1
00000
3 1
15 4
1100????????111
8 ?
1 0
4 1
11 ?
15 4
0????000?0???0?
6 0
10 0
1 ?
10 ?
15 2
???????0?0???0?
4 0
1 0
15 2
00000000?0???0?
4 ?
4 ?样例输出 复制
0
0
0
1
247
247
247
253
253
368
368
368
736
1664
3616
1760
880
0
24
24