2023icpc网络预选赛I. Pa?sWorD(dp)

题目给定字符串长度n以及字符串s

其中出现小写字母可以代表小写字母和大写字母  比如'a'可以代表'a'和'A'

出现'?'可以代表26个小写字母和26个大写字母和10个数字

出现大写字母和数字就是原本的数

同时要求大写字母，小写字母，数字一定都存在替换完的字符串中

相邻的字母不能相同

思路

dp[2][70][8]

第一维代表用来存前一个当前状态和前一个状态

70用来存当前的字符

0-25代表小写字母，26-51代表大写字母，52-61代表大写字母，62代表什么都没有也就是初始状态

8用二进制状态压缩存是否出现过大写，小写，数字

_ _ _第一个存是否出现大写，第二个小写，第三个数字

从前往后枚举

当出现'?'

枚举61中可能(i)，然后从前面62种状态(j)所有k继承

假如i是小写字母的话

如果i==j 就continue

其他情况dp[now][i][(k|(1<<2))]+=dp[pre][j][k]

同理i是大写的话就

dp[now][i][(k|(1<<1))]+=dp[pre][j][k]

但是这是一个o(64*64*8*100000)

会超时

你可以发现从前一个状态继承的就是62种状态之和减去唯一一个与当前转台不同的就行了

const int inf=0x3f3f3f3f3f3f3f3f,N=1e5+5,mod=998244353;
int dp[2][70][8];
int jian(int x,int y) {
	return ((x-y)%mod+mod)%mod;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	s=' '+s+' ';
	for(int i=1; i<=n; i++) {
		int now=i&1,pre=1-now;
		if(i==1) {
			dp[pre][62][0]=1;
		}
		for(int j=0; j<=62; j++) {
			for(int k=0; k<=7; k++) {
				dp[now][j][k]=0;
			}
		}
		vector<int>a(10);
		for(int j=0; j<=62; j++) {
			for(int k=0; k<=7; k++) {
				a[k]+=dp[pre][j][k];
				a[k]%=mod;
			}
		}
		if(s[i]=='?') {
			for(int j=0; j<26; j++) {
				for(int k=1; k<=7; k++) {
					for(int w=0; w<=7; w++) {
						if((w|(1<<2))==k) {
							dp[now][j][k]+=jian(a[w],dp[pre][j][w]);
							dp[now][j][k]%=mod;
						}
					}
				}
			}
			for(int j=26; j<52; j++) {
				for(int k=1; k<=7; k++) {
					for(int w=0; w<=7; w++) {
						if((w|(1<<1))==k) {
							dp[now][j][k]+=jian(a[w],dp[pre][j][w]);
							dp[now][j][k]%=mod;
						}
					}
				}
			}
			for(int j=52; j<62; j++) {
				for(int k=1; k<=7; k++) {
					for(int w=0; w<=7; w++) {
						if((w|(1<<0))==k) {
							dp[now][j][k]+=jian(a[w],dp[pre][j][w]);
							dp[now][j][k]%=mod;
						}
					}
				}
			}
		}
	else if(s[i]>='a'&&s[i]<='z') {
		for(int j=s[i]-'a'; j<=s[i]-'a'; j++) {
			for(int k=1; k<=7; k++) {
				for(int w=0; w<=7; w++) {
					if((w|(1<<2))==k) {
						dp[now][j][k]+=jian(a[w],dp[pre][j][w]);
						dp[now][j][k]%=mod;
					}
				}
			}
		}
		for(int j=s[i]-'a'+26; j<=s[i]-'a'+26; j++) {
			for(int k=1; k<=7; k++) {
				for(int w=0; w<=7; w++) {
					if((w|(1<<1))==k) {
						dp[now][j][k]+=jian(a[w],dp[pre][j][w]);
						dp[now][j][k]%=mod;
					}
				}
			}
		}
	} else if(s[i]>='A'&&s[i]<='Z') {
		int t=s[i]-'A'+26;
		for(int k=1; k<=7; k++) {
			for(int w=0; w<=7; w++) {
				if((w|(1<<1))==k) {
					dp[now][t][k]+=jian(a[w],dp[pre][t][w]);
					dp[now][t][k]%=mod;
				}
			}
		}
	} else {
		int t=s[i]-'0'+52;
		for(int k=1; k<=7; k++) {
			for(int w=0; w<=7; w++) {
				if((w|(1<<0))==k) {
					dp[now][t][k]+=jian(a[w],dp[pre][t][w]);
					dp[now][t][k]%=mod;
				}
			}
		}
	}
		// for(int i=0;i<62;i++){
		// 	for(int k=0;k<=7;k++){
		// 		cout<
		// 	}
		// 	cout<<"\n";
		// }
		// cout<<"--------------------\n";
}
int sum=0;
for(int i=0; i<62; i++) {
	sum+=dp[(n&1)][i][7];
	sum%=mod;
}
cout<"\n";
}