优美的字符串

Problem

Description

小X对字符串十分感兴趣。
对于一个只有0和1的字符串S，小X称其为优美的，当且仅当这个字符串最终可以通过不断的做下面的操
作变成"1"：

• 选择一个奇数 \(i(3 \le i \le |S|)\)。
• 将字符串的前i位与后面 \(|S| − i\) 位分开为 \(A\) 和 \(B\)。
• 不断的将 \(A\) 的后三位替换成 0 或者 1，具体的替换规则为将后三位看成一个二进制数 \(U\)，将他们替换成 \(f(U)\)。直到将 \(A\) 变成只剩下一位。
• 将 \(A\) 和 \(B\) 拼接起来得到新的 \(S\)。
  小X曾经写下了一个字符串，但现在这个字符串的某些位置已经丢失，现在小X想知道，重新在这些丢
  失的位置填上 0 或 1 后，有多少种可能能使这个字符串是优美的。由于可能性有很多，小X只需要你求出
  答案对 998244353 取模的值就好啦！

Input

第一行一个整数T,表示数据组数。
接下来每组数据第一行一个长度为8的01字符串，从前到后每一位分别为 \(f(000)\)，\(f(100)\)，\(f(010)\)，\(f(110)\)，
\(f(001)\)，\(f(101)\)，\(f(011)\)，\(f(111)\)。第二行一个只包含 '0','1','?' 的字符串表示询问。

Output

对于每组数据输出一行，表示答案。

Sample Input 1

1
10001100
0000001

Sample Output 1

1

Sample Input 2

1
11100111
???

Sample Output 2

6

Note

对于40%数据，输入中不包含’?’。其中20%数据满足 |S| ≤ 2000。
对于其他数据，15%数据满足|S| ≤ 20，30%数据满足|S| ≤ 2000。
对于100%数据，|S| ≤ 100000，|S|为奇数。

Solution

这是一道比较经典的 DP 套 DP。

首先看到这种题，我们首先想到的是在没有问号的情况下，某一个序列是否可行。我们考虑用 DP，设 \(f_{i,a,b}\) 表示序列第 \(i\) 个元素为 \(a(a=0/1)\)，前 \(i\) 个元素被化为 \(b(b=0/1)\) 是否可行。

对于每个 \(i\)，一定是从 \(i-2\) 进行转移，且分为两种，第一种是前 \(i-2\) 个已经转移好后再转移到 \(i\)，第二种是先合并 \(i-2,i-1,i\) 三个位置上的数，然后用合并好的数再和用 \(i-2\) 进行转移。转移方程如下：

\[f_{i,a,b}|=f_{i-2,F(s_{i-2},s_{i-1},a),b} \]

\[f_{i,a,b}|=f_{i-2,c}\times [F(c,s_{i-1},a)=b] \]

\(F\) 函数即为题目中用于合并的函数，\(a\) 和 \(c\) 分别枚举即可。

我们发现此时判断某个序列是否可行需要用 DP 的结果来判断而非直接通过某种状态进行判断，所以我们考虑把刚刚的 DP 设置为内层状态，即将 DP 的结果设为状态，状态的转移用内层 DP，此时我们只需要一个外层 DP 来转移答案。我们观察 DP 转移方程，发现只要我们知道 \(s_{i-2},f_{i-2,0,0},f_{i-2,0,1},f_{i-2,1,0},f_{i-2,1,1},s_{i-1},s_{i}\) 后就可以得出 \(f_{i,0/1,0/1}\) 的值。那么我们用一个五维状压记录 \(s_{i-2},f_{i-2,0,0},f_{i-2,0,1},f_{i-2,1,0},f_{i-2,1,1}\) 分别的值，然后枚举 \(s_{i-1},s_{i}\) （注意枚举合法性），就可以通过内层 DP 得出这一轮的状态。设上一轮状态为 \(S\)，转移后这一轮状态为 \(T\)，设 \(dp_{i,S}\) 表示在第 \(i\) 个位置状态为 \(S\) 的方案数。转移如下：

\[dp_{i-2,S}\to dp_{i,T} \]

最后统计答案时注意判断状态合法性。

Code

#include<bits/stdc++.h>
#define N 100005
#define int long long
#define mod 998244353
using namespace std;

int T,n;
int F[8],s[N];
int f[2][2],g[2][2],dp[N][32];
char str[N];

int num(int a,int b,int c){
	return (a<<2)+(b<<1)+c;
}
int val(int a,int b,int c,int d,int e){
	return (a<<4)+(b<<3)+(c<<2)+(d<<1)+e;
}
int get_s(int sn,int si1,int si){
	int si2=(sn&1);
	g[0][0]=g[0][1]=g[1][0]=g[1][1]=0;
	f[0][0]=((sn>>4)&1),f[0][1]=((sn>>3)&1),f[1][0]=((sn>>2)&1),f[1][1]=((sn>>1)&1);
	
	for(int b=0;b<2;b++){
		for(int a=0;a<2;a++){
			g[a][b]|=f[F[num(si2,si1,a)]][b];
			for(int c=0;c<2;c++)g[a][b]|=(f[si2][c]*(F[num(c,si1,a)]==b));
		}
	}
	
	return val(g[0][0],g[0][1],g[1][0],g[1][1],si);
}

signed main(){
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
	cin>>T;
	while(T--){
		char ch;
		for(int i=0;i<8;i++){
			cin>>ch;
			if(i==0)F[0]=ch-'0';
			else if(i==1)F[4]=ch-'0';
			else if(i==2)F[2]=ch-'0';
			else if(i==3)F[6]=ch-'0';
			else if(i==4)F[1]=ch-'0';
			else if(i==5)F[5]=ch-'0';
			else if(i==6)F[3]=ch-'0';
			else F[7]=ch-'0';
		}
		cin>>(str+1);
		n=strlen(str+1);
		for(int i=1;i<=n;i++){
			s[i]=str[i]-'0';
			if(s[i]!=0&&s[i]!=1)s[i]=-1;
		}
		if(s[1]!=-1)f[s[1]][s[1]]=1;
		else f[0][0]=f[1][1]=1;
		
		if(s[1]!=-1)dp[1][val(f[0][0],f[0][1],f[1][0],f[1][1],s[1])]=1;
		else dp[1][val(f[0][0],f[0][1],f[1][0],f[1][1],0)]=dp[1][val(f[0][0],f[0][1],f[1][0],f[1][1],1)]=1;
		
		for(int i=3;i<=n;i+=2){
			for(int sn=0;sn<32;sn++){
				if(!dp[i-2][sn])continue;
				for(int si1=0;si1<2;si1++){
					if(s[i-1]!=-1&&s[i-1]!=si1)continue;
					for(int si=0;si<2;si++){
						if(s[i]!=-1&&s[i]!=si)continue;
						int t=get_s(sn,si1,si);
						(dp[i][t]+=dp[i-2][sn])%=mod;
					}
				}
			}
		}
		int ans=0;
		for(int sn=0;sn<32;sn++){
			int si=(sn&1);
			if(s[n]!=-1&&s[n]!=si)continue;
			f[0][0]=((sn>>4)&1),f[0][1]=((sn>>3)&1),f[1][0]=((sn>>2)&1),f[1][1]=((sn>>1)&1);
			if(f[si][1])(ans+=dp[n][sn])%=mod;
		}
		cout<<ans<<"\n";
		memset(dp,0,sizeof dp);
		memset(f,0,sizeof f);
		memset(g,0,sizeof g);
	}
	return 0;
}