[acnoi2022] color ball

subject

Background （ The cruelest and truest reality , Often say it in the most playful way ）
“ Who doesn't like being $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ It's hanging , raise your hand , It's still too late to quit .”

If life could start over , I'll go back to where I never set foot $\mathrm{O}\mathrm{I}$ The time of . The sky is high and the emperor is far away , I am my own king . I control my body , Only take your own will as the standard .

Until that day , I'm sitting in that classroom , I can't see the interior of its original prison car . I heard that sentence again , Maybe this time , I will give different answers . Maybe I won't put my hands between my legs , Don't bear the coming three years $\mathrm{j}\mathrm{o}\mathrm{k}\mathrm{e}\mathrm{r}$ time , No use $\mathsf{F}\mathsf{i}\mathsf{r}\mathsf{e}\mathsf{W}\mathsf{i}\mathsf{n}\mathsf{g}\mathsf{B}\mathsf{i}\mathsf{r}\mathsf{d}$ Put on a smiling face to please it .

I slowly raised my hand , Trembling , Like a person dying , The last whine of stretching neck ……

“ Bang, ！”

Clap your hands heavily on the table .

“ Be hanged if you are hanged ！ Do you think I'll quit ？”

……

in endure Examination try . I and $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ Duel .

“ Everyone has his own efforts , This effort is indelible ！ Gossip $\cdot$ Sixty four violent search ！”

“ You use ‘ Strive ’ To make a perfunctory excuse , It's impossible to defeat me ！ Your fate is doomed to lose to me ！” $\mathsf{O}\mathsf{U}\mathsf{Y}\mathsf{E}$ Said , Rush to me ,“ Rolling escape $\cdot$$\mathsf{E}\mathsf{I}$ The soul of ！” I instantly lost consciousness .

He let me know , Fate is unchangeable .

……

The fourth provincial war broke out .

I stand $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ In front of , Two sharp wooden thorns ran straight through my chest . My heart is empty . I finally understand , So many people , Actively rush to death , That feeling of freedom …… On my forehead , The seal of those with bad habits is gradually disappearing ……

“ Why? …… You only sacrifice for me now ？” $\mathsf{D}\mathsf{D}(\mathsf{X}\mathsf{Y}\mathsf{X})$ Full of puzzles .

“ because …… You said I was …… genius .”

“ Didn't you say that you would never let your companions live ？” The sound comes from the gold medal pile $\mathsf{H}\mathsf{a}\mathsf{n}\mathsf{d}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{e}\mathsf{v}\mathsf{i}\mathsf{l}$ bring a person to the presence of sb. .“ I want you to say it again ！”

“ Look at the living companions around you ！ As long as you keep pretending to be weak , There will be more companions alive ！ Touch the corpse of your partner who is not yet cold , Enjoy it ！ In the end , The rest will only be the ones you are most familiar with 、 Is also the most afraid —— Huddle for warmth ！”

“ Come on , Come to me .” $\mathsf{H}\mathsf{a}\mathsf{n}\mathsf{d}\mathsf{I}\mathsf{n}\mathsf{D}\mathsf{e}\mathsf{v}\mathsf{i}\mathsf{l}$ Put out your hand .

Title Description
Black and white balls are lined up . You can execute several times “ eliminate ” operation , Every time “ eliminate ” The process is ：

• Take out a length of $n(2\nmid n)$ The prefix of , Remember it as $S$ .
• take $S$ Take out the last three balls . according to Some kind of rule , They will change into a ball . Put the ball back $S$ Tail of .
• Repeat the previous step , until $|S|=1$ . Put this ball back in front of the original ball sequence （ Pay attention to the original $S$ It has been taken out ）.

“ eliminate ” There is only one ball left , If the ball is white , Then this row of balls is “ good ​ Chromatic ”（ Be careful “ good ” It's shangsheng ）.

Now give me some balls , Some balls have unknown colors , ask , If you assign a color to all balls with unknown colors , How many cases are “ Lecherous ”. The answer is right $998244353$ modulus . Some kind of rule Will be given every time .

Data range and tips
The number of balls $⩽10^6$ .

Ideas

Always wanted to $\text{DFA}$, Then I feel numb . As a result, look at the solution , It seems very simple , I'm embarrassed .

need Linear scanning In order to count . Transform directly according to the meaning of the topic ： The ball that has been swept so far , Save up . Add two balls each time , To operate , Empty the balls in the stack , Become a ball ; Otherwise, join yourself .

It doesn't matter how the stack looks , Because the result is just a ball , Only need to use $*a,b*$ You can store , When the newly added ball is white or black , What color ball will change after one operation . Such a function has only $2^2$ individual , The problem of judgment , You can use it $2^{2^2}$ Shape pressure indicates whether each function can be summed up .

The same goes for counting . It can be extended to $m$ Two colors , The complexity is $\mathcal{O}(m^2{2}^{m^m}n)$ .

Code

#include <cstdio> // JZM yydJUNK!!!
#include <iostream> // XJX yyds!!!
#include <algorithm> // XYX yydLONELY!!!
#include <cstring> // (the STRONG long for LONELINESS)
#include <cctype> // ZXY yydSISTER!!!
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MAXN = 100005, MOD = 998244353;
inline void modAddUp(int &x, const int &y){
    
	if((x += y) >= MOD) x -= MOD;
}

int trans[2][2][1<<4], dp[2][1<<4];
char mov[15], str[MAXN];
int main(){
    
	for(int T=readint(); T; --T){
    
		scanf("%s",mov);
		rep(a,0,1) rep(b,0,1) rep(c,0,1) rep(d,0,1){
    
			// when function is <c,d>, push_back(a,b)
			{
     // if operate @a a here
				int ass = a ? d : c; // become <ass,b>
				const int zero = mov[ass^(b<<1)]^48;
				const int one = mov[ass^(b<<1)^4]^48;
				trans[a][b][1<<(c^(d<<1))] = 1<<(zero^(one<<1));
			}
			{
     // if not to operate @a a here
				const int zero = (mov[a|(b<<1)]^48) ? d : c;
				const int one = (mov[a|(b<<1)|4]^48) ? d : c;
				trans[a][b][1<<(c^(d<<1))] |= 1<<(zero^(one<<1));
			}
		}
		rep(a,0,1) rep(b,0,1) rep(S,1,(1<<4)-1)
			trans[a][b][S] = trans[a][b][S&(S-1)]|trans[a][b][S&-S];
		scanf("%s",str); int n = int(strlen(str))-1;
		memset(dp[0],0,(1<<4)<<2), dp[0][1<<2] = 1;
		for(int i=0,nxt=1; i!=n; i+=2,nxt^=1){
    
			memset(dp[nxt],0,(1<<4)<<2);
			rep(a,0,1) if((str[i]^48) != (a^1))
			rep(b,0,1) if((str[i+1]^48) != (b^1))
				rep(S,1,(1<<4)-1) modAddUp(
					dp[nxt][trans[a][b][S]],dp[nxt^1][S]);
		}
		int ans = 0;
		rep(c,0,1) if((str[n]^48) != (c^1))
			rep(S,1,(1<<4)-1){
    
				bool ok = false;
				rep(a,0,1) rep(b,0,1) if(S>>(a^(b<<1))&1)
					if((c ? b : a) == 1) ok = true;
				if(ok) modAddUp(ans,dp[(n>>1)&1][S]);
			}
		printf("%d\n",ans);
	}
	return 0;
}