模板串计数禁三回文
2026-02-07 14:13:26
发布于：浙江
10阅读
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;
}
有帮助，赞一个