模板串计数禁三回文

hopeless

2026-02-07 14:13:26

发布于：浙江

9阅读

0回复

0点赞

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=998244353;
ll add(ll a,ll b){
	return (a%mod+b%mod)%mod;
}
ll mul(ll a,ll b){
	return (a%mod)*(b%mod)%mod;
}
pair<string,string> ss(string s){
	string a,b;
	for(char i:s){
		a.push_back(i);
		swap(a,b);
	}
	return {a,b};
}
ll dp(string s){
    int len=s.length();
    if(len==0) return 1;
	vector<vector<ll> > f(len+1,vector<ll>(30));
	s=" "+s;
	if(s[1]=='?')
		for(int i=0;i<26;++i) f[1][i]=1;
	else f[1][s[1]-'A']=1;
	for(int i=2;i<=len;++i){
		if(s[i]=='?'){
			for(int j=0;j<26;++j){
				for(int l=0;l<26;++l){
					if(j==l) continue;
					f[i][j]=add(f[i][j],f[i-1][l]);
				}
			}
		}
		else{
			int j=s[i]-'A';
			for(int l=0;l<26;++l){
				if(j==l) continue;
				f[i][j]=add(f[i][j],f[i-1][l]);
			}
		}
	}
	ll ans=0;
	for(int i=0;i<26;++i)
		ans=add(ans,f[len][i]);
	return ans;
}
int main(){
    int n;string s;
	cin>>n>>s;
	auto [a,b]=ss(s);
	cout<<mul(dp(a),dp(b));
	return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 2

蒋皓轩
666

2026-02-07 来自浙江
1
huchen
delicious

2026-02-07 来自浙江
1

全部评论 2

热门讨论