4. 【模拟赛1】模板串计数禁三回文
2026-02-07 14:13:47
发布于：浙江
7阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
i64 mod=998244353;
int N;
i64 add(i64 a,i64 b){
return (a+b)%mod;
}
i64 mul(i64 a,i64 b){
return (a*b)%mod;
}
pair<string,string> ss(string s){
string a,b;
for(auto i:s){
a.push_back(i);
swap(a,b);
}
return {a,b};
}
i64 dp(string s){
int n=s.length();
vector<vector<i64>> f(n+1,vector<i64>(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<=n;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]);
}
}
}
i64 ans=0;
for(int i=0;i<26;i++){
ans=add(ans,f[n][i]);
}
return ans;
}
int main(){
cin>>N;
if(N==1){
cout<<26;
return 0;
}
string s;cin>>s;
cout<<mul(dp(ss(s).first),dp(ss(s).second));
return 0;
}
```cpp
```cpp
有帮助，赞一个