题目大意
给定一个字符串s，其中只包含小写字母，大写字母，数字和问号$?$。可以进行一下操作：
- 将小写字母变为相对应的大写字母或不变；
- 将问号$?$变为大写字母，小写字母或数字中的任意一个字符。
要求满足以下条件的所有方案数的数量：
- 字符串中至少有一个小写字母；
- 字符串中至少有一个大写字母；
- 字符串中至少有一个数字；
- 字符串中任意相邻字符不能相同。
解题思路
先考虑简单的三维$dp[i][j][k]$，表示第$i$个字符为$j$且前$i$个字符中各种字符的存在状态为$k$的合法数量。
其中$k$为一个三位二进制数，如：
- 100表示只存在数字；
- 010表示只存在大写字母；
- 001表示只存在小写字母。
剩余状态也是类似的道理。
然后考虑状态转移，转移的过程只有一个限制条件，即相邻字符不能相同，则状态转移如下：
$$dp[i][x][k|t]=dp[i-1][j][k],x!=j$$
其中，当$x$分别为小写字母，大写字母，数字的时候$t$分别为$1$，$2$，$4$。
假设当前遍历到小写字母，则当它为大、小写字母的时候分别进行状态转移；假设遍历到问号，则遍历所有可以变成的字符进行转移。
时间复杂度（O(n*8*8*70)）空间复杂度（O(n*8*8*70)）
真巧，全都超限。
对于空间复杂度，仔细观察转移方程发现，第$i$项只第$i-1$项有关，故可以考虑滚动数组优化；至于时间复杂度，则可以考虑使用差分优化。
参考代码
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
| #include<bits/stdc++.h>
#define maxn 70
#define mod 998244353
using namespace std;
int d[maxn][1<<3],g[maxn][1<<3],dis[1<<3][maxn];
map<char,int>num;
void init(){
int cur=0;
for(int i='a';i<='z';++i) num[char(i)]=++cur;
for(int i='A';i<='Z';++i) num[char(i)]=++cur;
for(int i='0';i<='9';++i) num[char(i)]=++cur;
num['?']=1000;
}
void solve() {
int n,ans=0; cin >> n;
string s; cin >> s;
s=" "+s;
d[0][0]=1;
for(int i=1;i<=n;++i){
memcpy(g,d,sizeof(d));
memset(dis,0,sizeof(dis));
memset(d,0,sizeof(d));
for(int j=0;j<=62;++j){
for(int state=0;state<8;++state){
if(!g[j][state]||num[s[i]]==j&&num[s[i]]>=27) continue;
int tmp=g[j][state];
if(s[i]=='?'){
int sta=state|1;
if(j>=1&&j<=26) dis[sta][1]=(dis[sta][1]+tmp)%mod,dis[sta][j]=(dis[sta][j]-tmp)%mod,dis[sta][j+1]=(dis[sta][j+1]+tmp)%mod,dis[sta][27]=(dis[sta][27]-tmp)%mod;
else dis[sta][1]=(dis[sta][1]+tmp)%mod,dis[sta][27]=(dis[sta][27]-tmp)%mod;
sta=state|2;
if(j>=27&&j<=52) dis[sta][27]=(dis[sta][27]+tmp)%mod,dis[sta][j]=(dis[sta][j]-tmp)%mod,dis[sta][j+1]=(dis[sta][j+1]+tmp)%mod,dis[sta][53]=(dis[sta][53]-tmp)%mod;
else dis[sta][27]=(dis[sta][27]+tmp)%mod,dis[sta][53]=(dis[sta][53]-tmp)%mod;
sta=state|4;
if(j>=53&&j<=62) dis[sta][53]=(dis[sta][53]+tmp)%mod,dis[sta][j]=(dis[sta][j]-tmp)%mod,dis[sta][j+1]=(dis[sta][j+1]+tmp)%mod,dis[sta][63]=(dis[sta][63]-tmp)%mod;
else dis[sta][53]=(dis[sta][53]+tmp)%mod,dis[sta][63]=(dis[sta][63]-tmp)%mod;
}
else if(num[s[i]]<=26){
int cur=num[s[i]],sta=state|1;
if(cur!=j) d[cur][sta]=(d[cur][sta]+tmp)%mod;
cur=num[s[i]]+26,sta=state|2;
if(cur!=j) d[cur][sta]=(d[cur][sta]+tmp)%mod;
}
else if(num[s[i]]<=62&&num[s[i]]>=27){
int cur=num[s[i]],sta;
if(cur>=27&&cur<=52) sta=state|2;
else if(cur>=53&&cur<=62) sta=state|4;
d[cur][sta]=(d[cur][sta]+tmp)%mod;
}
}
}
for(int state=0;state<8;++state){
int cur=0;
for(int j=1;j<=62;++j){
cur=(cur+dis[state][j])%mod;
d[j][state]=(d[j][state]+cur)%mod;
}
}
}
for(int i=1;i<=65;++i) ans=(ans+d[i][7])%mod;
cout << (ans%mod+mod)%mod << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
if(fopen("in.txt", "r")) {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
init();
int t=1;
while(t--) {
solve();
}
return 0;
}
|
