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<<dp[now][i][k]<<' ';// 	}// 	cout<<"\n";// }// cout<<"--------------------\n";
}
int sum=0;
for(int i=0; i<62; i++) {sum+=dp[(n&1)][i][7];sum%=mod;
}
cout<<sum<<"\n";
}