背景

一普朗克时间是 $10^{-43}s$ ，我应该以怎样的速度，才能将答案求出
……
《对出题人的拷问》

题面

$1\le T\le 10,1\le n\le 10^5$ 。

题解

你可以看到，这道题将状态的转移随意制定，并输入给你。

一般这种定制转移的题如果毫无思路，可以往自动机上想。

如果我们选择了一段前缀，将它转化成一个球，我们需要从后往前依次扫描三个球，得出一个球，相当于拿最后一个球，依次往前吃两个球、改变颜色。

所以对于直接从后往前吃的情况，我们可以建出一个只有两个点的非确定性有穷自动机，每条转移边都是两个球：

那考虑到我们可以先选择中间的某个前缀，合并成一个某颜色的球，再和后面的考虑，所以我们吞了两个球时（假定此时有三个球 $x,y,z$，目标为 a(=0/1)），还有一个方向，那就是假定最前面的那个球 $x$ 与以后要吞的所有球合并，再与后面两个球合并，那么我们考虑 $x$ 结果为 1 或 0 时分别能否与 $y,z$ 合并成 $a$，如果可以，就能分别向【当前为 $x$ 目标为 1】和【当前为 $x$ 目标为 0】转移。于是我们得出一个 4 个点的非确定性有穷自动机。

现在我们就有 4 个点，我们把它变成确定性有穷自动机就可以DP转移了！方法就是状压，$2^4=16$ 个节点，表示状态集。

时间复杂度 $O(Tn\cdot 16)$ 。

CODE

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<random>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB long double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
int xchar() {static const int maxn = 1000000;static char b[maxn];static int pos = 0,len = 0;if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);if(pos == len) return -1;return b[pos ++];
}
//#define getchar() xchar()
LL read() {LL f = 1,x = 0;int s = getchar();while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
void putnum(LL x) {if(!x) {putchar('0');return ;}if(x<0) putchar('-'),x = -x;return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}const int MOD = 998244353;
int n,m,s,o,k;
char a[MAXN];
bool rs[10];
int rev[10];
int dp[MAXN][16];
int tr[16][4];
int main() {freopen("game.in","r",stdin);freopen("game.out","w",stdout);int T = read();while(T --) {char ss[10];scanf("%s",ss);for(int i = 0;i < 8;i ++) {rs[i] = ss[i]-'0';if(i) rev[i] = (rev[i>>1]>>1) | ((i&1) ? 4:0);if(i && rev[i] < i) swap(rs[i],rs[rev[i]]);
//			printf("rev[%d] = %d\n",i,rev[i]);}
//		for(int i = 0;i < 8;i ++) putchar('0'+rs[i]);ENDL;for(int i = 1;i < 16;i ++) {for(int j = 0;j < 4;j ++) {int to = 0;if(i&1) {to |= 1<<rs[j<<1];int k = (j<<1)&3,k2 = j>>1;if(!rs[k|4]) to |= 1<<(2+k2);if(!rs[k]) to |= 1<<k2;}if(i&2) {to |= 1<<rs[j<<1|1];int k = (j<<1|1)&3,k2 = j>>1;if(!rs[k|4]) to |= 1<<(2+k2);if(!rs[k]) to |= 1<<k2;}if(i&4) {to |= 1<<(2+rs[j<<1]);int k = (j<<1)&3,k2 = j>>1;if(rs[k|4]) to |= 1<<(2+k2);if(rs[k]) to |= 1<<k2;}if(i&8) {to |= 1<<(2+rs[j<<1|1]);int k = (j<<1|1)&3,k2 = j>>1;if(rs[k|4]) to |= 1<<(2+k2);if(rs[k]) to |= 1<<k2;}tr[i][j] = to;}}scanf("%s",a + 1);n = strlen(a + 1);memset(dp[1],0,sizeof(dp[1]));for(int i = 1;i < 16;i ++) {if((i&1) || (i&8)) dp[1][i] = 1;}for(int i = 3;i <= n;i += 2) {memset(dp[i],0,sizeof(dp[i]));for(int nm = 0;nm < 4;nm ++) {if(((nm&1) && a[i-1] == '0') || (!(nm&1) && a[i-1] == '1')) continue;if(((nm&2) && a[i-2] == '0') || (!(nm&2) && a[i-2] == '1')) continue;for(int j = 1;j < 16;j ++) {(dp[i][j] += dp[i-2][tr[j][nm]]);if(dp[i][j] >= MOD) dp[i][j] -= MOD;}}
//			for(int j = 1;j < 16;j ++) {
//				if(dp[i][j]) printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
//			}}int ans = 0;if(a[n] != '1') ans += dp[n][4];if(a[n] != '0') ans += dp[n][8];ans %= MOD;AIput(ans,'\n');}return 0;
}