P8433 题解
dAniel_lele
·
·
题解
看官方是 O(n^2) 的，我来一发 O(n) 解法。
思路
考虑 dp_{i,1/2/3}，依次表示看到第 i 位，不属于任何 [] 中；属于一个 [] 中且目前该括号内没有字母或数字；属于一个 [] 中且目前该括号内有若干字母或数字。
考虑转移：
若s_i='?'：dp_{i,1}+=dp_{i-1,1}\times36,dp_{i,3}+=(dp_{i-1,2}+dp_{i-1,3})\times36。
若s_i\not='?'：dp_{i,1}+=dp_{i-1,1},dp_{i,3}+=(dp_{i-1,2}+dp_{i-1,3})。
* 这一位放置一个 `]`：
$dp_{i,1}+=dp_{i-1,3}$。
$dp_{i+1,1}+=dp_{i-1,3}\times2$。
* 这三个位置放置一对 `<x>-<y>`：
考虑 $s_i$ 和 $s_{i+2}$ 是 数字/字母/问号，依次枚举即可。
如果 $s_i$ 和 $s_{i+2}$ 均为问号，方案数为 $\binom{26}{2}+\binom{10}{2}$。
若其中一个是问号，只需用另一个减去边界即可。
如果全是填出的 数字/字母，直接判断是否可行即可
时间复杂度 $O(n)$。
## 代码
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int dp[10000005][4];
signed main(){
string s;
cin>>s;
dp[0][1]=1;
s=" "+s;
for(int i=1;i<s.size();i++){
if((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')){
dp[i][1]=(dp[i][1]+dp[i-1][1])%mod;
dp[i][3]=(dp[i][3]+dp[i-1][2]+dp[i-1][3])%mod;
}
if(s[i]=='?'){
dp[i][1]=(dp[i][1]+dp[i-1][1]*36)%mod;
dp[i][3]=(dp[i][3]+dp[i-1][2]*36+dp[i-1][3]*36)%mod;
}
if(s[i]=='['||s[i]=='?'){
dp[i][2]=(dp[i][2]+dp[i-1][1])%mod;
}
if(s[i]==']'||s[i]=='?'){
dp[i][1]=(dp[i][1]+dp[i-1][3])%mod;
if((i!=(s.size()-1))&&(s[i+1]=='*'||s[i+1]=='?')) dp[i+1][1]=(dp[i+1][1]+dp[i-1][3])%mod;
if((i!=(s.size()-1))&&(s[i+1]=='+'||s[i+1]=='?')) dp[i+1][1]=(dp[i+1][1]+dp[i-1][3])%mod;
}
if((i<(s.size()-2))&&(s[i+1]=='-'||s[i+1]=='?')){
if(s[i]=='?'&&s[i+2]=='?'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*370+dp[i-1][3]*370)%mod;
}
if(s[i]=='?'&&s[i+2]>='0'&&s[i+2]<='9'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*(s[i+2]-'0')+dp[i-1][3]*(s[i+2]-'0'))%mod;
}
if(s[i]=='?'&&s[i+2]>='a'&&s[i+2]<='z'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*(s[i+2]-'a')+dp[i-1][3]*(s[i+2]-'a'))%mod;
}
if(s[i+2]=='?'&&s[i]>='0'&&s[i]<='9'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*('9'-s[i])+dp[i-1][3]*('9'-s[i]))%mod;
}
if(s[i+2]=='?'&&s[i]>='a'&&s[i]<='z'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*('z'-s[i])+dp[i-1][3]*('z'-s[i]))%mod;
}
if(s[i+2]>='a'&&s[i+2]<='z'&&s[i]>='a'&&s[i]<='z'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*(s[i]<s[i+2])+dp[i-1][3]*(s[i]<s[i+2]))%mod;
}
if(s[i+2]>='0'&&s[i+2]<='9'&&s[i]>='0'&&s[i]<='9'){
dp[i+2][3]=(dp[i+2][3]+dp[i-1][2]*(s[i]<s[i+2])+dp[i-1][3]*(s[i]<s[i+2]))%mod;
}
}
}
cout<<dp[s.size()-1][1];
}
```
## 建议
建议加强数据加一个 $0$ 分的 $\text{Subtask}$。
感谢出题人的迅速回应，题解已修改为新数据可通过的代码了。