题解：P17236 『STA - R10』刷墙墙刷

sbno333 · 2026-08-11 21:03:33 · 题解

什么序列合法？

首先，如果至少进行一次操作，最终得到的 b 要求必然存在一个长为 3 的回文子串，即存在 i，满足 b_i=b_{i+2}。

另外，我们找到这个串之后，可以最后更新这里，发现两边可以分别从边缘往这里通过赋值一个最后一个字符正确的长为 3 的字符串来操作，最后把这部分覆盖上，因为覆盖前别人怎么操作你并不关心对这里的影响。

于是条件就是不进行操作或者存在 b_i=b_{i+2}，前者容易计数，但注意如果和后面重复就不能算。

对于后者，我们首先把它变为不存在，就是总数减去不存在，然后随便一个方法比如 O(26n) 的 dp 就能解决。

我们奇偶分类，每一类相邻两项不同，互不干涉，然后一项直接设 dp_{i,j} 表示考虑前 i 个，第 i 个是 j 的方案数即可，容易转移。

不过这个题其实可以严格线性，但似乎没有前者好实现，这里不过多赘述。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
string a,b;
int dp[26][1000009];
signed main(){
    int n;
    cin>>n;
    cin>>a>>b;
    int ans;
    ans=1;
    for(int i=0;i<n;i++){
        if(a[i]!=b[i]&&(b[i]!='?')){
            ans=0;
            break;
        }
        if(i>1&&a[i]==a[i-2]){
            ans=0;
            break;
        }
    }
    int sum;
    sum=1;
    for(int i=0;i<n;i++){
        if(b[i]=='?'){
            sum*=26,sum%=mod;
        }
    }
    ans+=sum;
    ans%=mod;
    sum=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<26;j++){
            dp[j][i]=0;
        }
        if(i==0||i==1){
            if(b[i]=='?'){
                for(int j=0;j<26;j++){
                    dp[j][i]=1;
                }
            }else{
                dp[b[i]-'a'][i]=1;
            }
        }else{
            int sum;
            sum=0;
            for(int j=0;j<26;j++)sum+=dp[j][i-2],sum%=mod;
            if(b[i]=='?'){
                for(int j=0;j<26;j++){
                    dp[j][i]=(sum-dp[j][i-2]+mod)%mod;
                }
            }else{
                dp[b[i]-'a'][i]=(sum-dp[b[i]-'a'][i-2]+mod)%mod;
            }
        }
    }
    int u,v;
    u=v=0;
    for(int i=0;i<26;i++){
        v+=dp[i][n-1];
        v%=mod;
    }
    if(n==1){
        u=1;

    }else{
        for(int i=0;i<26;i++){
            u+=dp[i][n-2];
            u%=mod;
        }
    }
    sum=u*v;
    sum%=mod;
    cout<<(ans-sum+mod)%mod;
    return 0;
}