dp转自动机：1017T4

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133894734

http://cplusoj.com/d/senior/p/SS231017D

求本质不同子序列个数见 https://blog.csdn.net/zhangtingxiqwq/article/details/133885358

发现这就是交换 gg 和 fif_i 的奇偶性。

我们发现本质不同的 ff 状态只有4种，我们可以基于这个建一个自动机

这样子我们就可以统计让每个子串在这个自动机上跑，求出其本质不同子序列个数

然后我们一个串的所有子串。

我们可以记录一个 242^4 的状态，表示所有后缀在自动机1上每个节点分别有多少个（只需要记录0/1）

我们发现还要再记多一个状态表示前面的所有子串的奇偶性

我们发现这个过程可以建自动机2

然后询问每个串直接在自动机2上跑就行了

正解还要用猫树分治优化，但我不会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 50010
//#define M
#define mo 998244353
void Add(int &a, int b) {
	a+=b; if(a>=mo || a<=-mo) a%=mo; 
    if(a<0) a+=mo; 
}
int n, m, i, j, k, T;
int ans, s, nxtA[5][5], nxtB[50][5]; 
int f[50], g[50], p[50], q, Ans; 
int l, r; 
char str[N]; 
vector<int>G[128]; 

void init() {
	nxtA[0][0]=1; nxtA[0][1]=2; nxtA[0][2]=3; 
	nxtA[1][0]=0; nxtA[1][1]=1; nxtA[1][2]=1; 
	nxtA[2][0]=2; nxtA[2][1]=0; nxtA[2][2]=2; 
	nxtA[3][0]=3; nxtA[3][1]=3; nxtA[3][2]=0; 
	vector<int>c, d; c.resize(4); d.resize(4); 
	for(i=0; i<32; ++i) {
		c[0]=(i>>0)&1; c[1]=(i>>1)&1; c[2]=(i>>2)&1; c[3]=(i>>3)&1; Ans=(i>>4)&1; 
		Ans^=c[0]; p[i]=Ans; 
		for(k=0; k<=2; ++k) { //转移边是k 
			d[0]=d[1]=d[2]=d[3]=0; d[k+1]^=1; 
			for(j=0; j<=3; ++j) d[nxtA[j][k]]^=c[j]; 
			s=(d[0]<<0)+(d[1]<<1)+(d[2]<<2)+(d[3]<<3)+(Ans<<4); 
			nxtB[i][k]=s; 
//			printf("nxtB[%lld][%lld] = %lld\n", i, k, nxtB[i][k]); 
//			printf("%lld %lld %lld\n", i, nxtB[i][k], k); 
		}
//		printf("%lld %lld\n", i, p[i]); 
	}
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	freopen("replace.in", "r", stdin);
	freopen("replace.out", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	init(); n=read(); 
	scanf("%s", str+1); q=read(); 
	G['0']={0}; G['1']={1}; G['2']={2}; 
	G['a']={0, 1}; G['b']={0, 2}; G['c']={1, 2}; 
	G['?']={0, 1, 2}; 
//	for(s=0; s<32; ++s) printf("%2lld", s); printf("\n"); 
//	for(s=0; s<32; ++s) printf("%lld ", p[s]); printf("\n\n"); 
	while(q--) {
		l=read(); r=read(); 
		memset(f, 0, sizeof(f)); 
		memset(g, 0, sizeof(g)); 
		f[0]=1; ans=0; 
		for(i=r; i>=l; --i) {
			for(s=0; s<32; ++s) 
				for(auto j : G[str[i]]) Add(g[nxtB[s][j]], f[s]); 
			memcpy(f, g, sizeof(g)); 
			memset(g, 0, sizeof(g)); 
//			for(s=0; s<32; ++s) printf("%lld ", f[s]); printf("\n"); 
		}
		for(s=0; s<32; ++s) if(p[s]) Add(ans, f[s]); 
		printf("%lld\n", ans); 
	}
	return 0;
}