培训中心网站建设论文,网络营销十大成功案例,html做网站实战教程,wordpress 自带主题题目给定字符串长度n以及字符串s
其中出现小写字母可以代表小写字母和大写字母 比如a可以代表a和A
出现?可以代表26个小写字母和26个大写字母和10个数字
出现大写字母和数字就是原本的数
同时要求大写字母#xff0c;小写字母#xff0c;数字一定都存在替换完的字符串中…题目给定字符串长度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是小写字母的话
如果ij 就continue
其他情况dp[now][i][(k|(12))]dp[pre][j][k]
同理i是大写的话就
dp[now][i][(k|(11))]dp[pre][j][k]
但是这是一个o(64*64*8*100000)
会超时
你可以发现从前一个状态继承的就是62种状态之和减去唯一一个与当前转台不同的就行了
const int inf0x3f3f3f3f3f3f3f3f,N1e55,mod998244353;
int dp[2][70][8];
int jian(int x,int y) {return ((x-y)%modmod)%mod;
}
signed main() {ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n;cinn;string s;cins;s s ;for(int i1; in; i) {int nowi1,pre1-now;if(i1) {dp[pre][62][0]1;}for(int j0; j62; j) {for(int k0; k7; k) {dp[now][j][k]0;}}vectorinta(10);for(int j0; j62; j) {for(int k0; k7; k) {a[k]dp[pre][j][k];a[k]%mod;}}if(s[i]?) {for(int j0; j26; j) {for(int k1; k7; k) {for(int w0; w7; w) {if((w|(12))k) {dp[now][j][k]jian(a[w],dp[pre][j][w]);dp[now][j][k]%mod;}}}}for(int j26; j52; j) {for(int k1; k7; k) {for(int w0; w7; w) {if((w|(11))k) {dp[now][j][k]jian(a[w],dp[pre][j][w]);dp[now][j][k]%mod;}}}}for(int j52; j62; j) {for(int k1; k7; k) {for(int w0; w7; w) {if((w|(10))k) {dp[now][j][k]jian(a[w],dp[pre][j][w]);dp[now][j][k]%mod;}}}}}else if(s[i]as[i]z) {for(int js[i]-a; js[i]-a; j) {for(int k1; k7; k) {for(int w0; w7; w) {if((w|(12))k) {dp[now][j][k]jian(a[w],dp[pre][j][w]);dp[now][j][k]%mod;}}}}for(int js[i]-a26; js[i]-a26; j) {for(int k1; k7; k) {for(int w0; w7; w) {if((w|(11))k) {dp[now][j][k]jian(a[w],dp[pre][j][w]);dp[now][j][k]%mod;}}}}} else if(s[i]As[i]Z) {int ts[i]-A26;for(int k1; k7; k) {for(int w0; w7; w) {if((w|(11))k) {dp[now][t][k]jian(a[w],dp[pre][t][w]);dp[now][t][k]%mod;}}}} else {int ts[i]-052;for(int k1; k7; k) {for(int w0; w7; w) {if((w|(10))k) {dp[now][t][k]jian(a[w],dp[pre][t][w]);dp[now][t][k]%mod;}}}}// for(int i0;i62;i){// for(int k0;k7;k){// coutdp[now][i][k] ;// }// cout\n;// }// cout--------------------\n;
}
int sum0;
for(int i0; i62; i) {sumdp[(n1)][i][7];sum%mod;
}
coutsum\n;
}
