自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 22:39:00，当前版本为作者最后更新于2022-03-24 20:06:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看官方是 $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,2}+=dp_{i-1,1}$。

• 这一位放置一个 ]：

$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)$。

代码

#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}$。

感谢出题人的迅速回应，题解已修改为新数据可通过的代码了。