济宁网站建设是什么,江苏省建筑网监督信息平台,百度网站的优缺点,网站开发淄博problem
solution
可以从 DFA\text{DFA}DFA 的思想来考虑这道题。
考虑建一个 DFA\text{DFA}DFA 只接受最后可以变成字符串 111 的原串。
因为每次是选择三个 连续/相邻 的位置操作#xff0c;限制是比较强的#xff0c;无非有三种情况。
case1 三个全 111#xff0c;操…problem
solution
可以从 DFA\text{DFA}DFA 的思想来考虑这道题。
考虑建一个 DFA\text{DFA}DFA 只接受最后可以变成字符串 111 的原串。
因为每次是选择三个 连续/相邻 的位置操作限制是比较强的无非有三种情况。
case1 三个全 111操作后只剩 111 个 111相当于删去两个 111。case2 三个全 000操作后只剩 111 个 000相当于删去两个 000。case3 剩下的组合操作后只剩 111 个 0/10/10/1但都相当于删去 010101 各一个。
显然贪心地我们是不会操作 case1 减少 111 的数量的。而连续的 000 的数量也不会超过 222 个超过一定可以操作回来。
只有 111 的数量大于等于 000 的数量就是合法的。
事实上最后情况 111 的数量绝对不可能跟 000 数量相同因为题目保证输入串是奇数长度而每次的操作都减少两个长度。
111 多了反正都会被接受没必要在 DFA\text{DFA}DFA 上建立这么多状态。
我们将所有 111 的个数超过两个的状态都连回个数为 222 的状态然后接受这个状态即可。
所以 DFA\text{DFA}DFA 的状态数是 1(0/1/2)−0(0/1/2)3⋅391(0/1/2)-0(0/1/2)3·391(0/1/2)−0(0/1/2)3⋅39 种的。
最后就是在这个 DFA\text{DFA}DFA 上跑 dpdpdp 即可。
设 f(i,j,k):f(i,j,k):f(i,j,k): 到字符串的第 iii 位此时状态为 jjj 个 111 和 kkk 个 000 的方案数。考虑向 i1i1i1 位转移。
si10s_{i1}0si10直接增加 000 个个数即可。 k2k2k2case2 操作。f(i,j,2)→f(i1,j,0)f(i,j,2)\rightarrow f(i1,j,0)f(i,j,2)→f(i1,j,0)。k≠2k\neq 2k2f(i,j,k)→f(i1,j,k1)f(i,j,k)\rightarrow f(i1,j,k1)f(i,j,k)→f(i1,j,k1)。 si11s_{i1}1si11。在这个时候才考虑跟 000 的抵消情况。 k0k0k0f(i,j,0)→f(i1,min(j1,2),0)f(i,j,0)\rightarrow f(i1,\min(j1,2),0)f(i,j,0)→f(i1,min(j1,2),0)。k≠0k\neq 0k0case3 操作f(i,j,k)→f(i,j,k−1)f(i,j,k)\rightarrow f(i,j,k-1)f(i,j,k)→f(i,j,k−1)。 si1?s_{i1}?si1?将上面两种情况都跑一遍即可。
code
#include bits/stdc.h
using namespace std;
#define mod 1000000007
#define int long long
#define maxn 300005
char s[maxn];
int n, ans;
int f[maxn][3][3];signed main() {scanf( %s, s 1 );n strlen( s 1 );f[0][0][0] 1;//f[i][j][k]:到字符串第i位时 有j个1 k个0for( int i 0;i n;i ) {if( s[i 1] ! 0 ) {for( int j 0;j 2;j ) {( f[i 1][j][0] f[i][j][1] ) % mod;( f[i 1][j][1] f[i][j][2] ) % mod;( f[i 1][min( j 1, 2ll )][0] f[i][j][0] ) % mod;}}if( s[i 1] ! 1 ) {for( int j 0;j 2;j ) {( f[i 1][j][1] f[i][j][2] ) % mod;( f[i 1][j][2] f[i][j][1] ) % mod;( f[i 1][j][1] f[i][j][0] ) % mod;}}}for( int i 0;i 2;i )for( int j 0;j i;j )( ans f[n][i][j] ) % mod; printf( %lld\n, ans );return 0;
}
