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

Steady_Steve · 2026-08-11 19:46:33 · 题解

竟然是容斥原理，吓哭了。

解题思路

每次操作选定一个 L\ge 3 的奇数区间，替换成一个回文串。

• 如果 L=3，替换后的字符串一定有 b_i=b_{i+2}。
• 如果 L>3，中心三个字符同样也必然构成一个长度为 3 的回文串（即 b_{mid-1}=b_{mid+1}）。

那么我们就得到结论： 最终字符串 b 中必然存在长度为 3 的回文子串。

由于方案数只取决于字符串中的 ?，所以我们考虑容斥。 我们设：

• 全集：所有填充 ? 的方案数，即 26^q（q 为问号个数）
• 坏情况：填充后，既不等于 a，也不存在 b_i=b_{i+2}。
• 等于 a 的情况：填充后恰好等于 a。
• 上一种情况，但有回文：a 本身就存在 b_i=b_{i+2}

那么最终答案就等于 全集 - 坏方案 + 等于 a 的方案 - 等于 a 且含回文的方案。

那么，问题的难点就在于如何计算坏情况的数量。

由于约束条件只约束间隔为 2 的字符，那么字符串奇偶位置的字符一定完全独立。

考虑对奇偶分开进行 DP：

• 转移方程：当前位置只能填与上一个位置不同的字母。

最后坏情况的答案即为 \sum_{i = 0}^{25} dp_i。

注意 26^q 用快速幂求解即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,mod=998244353;
bool flag=true,rep=false;
string a,b,od,ev;
int qpow(int a,int p){
    int res=1;
    while(p){
        if(p&1) res=res*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return res;
}
int calc(string s){
    int dp[101]={0};
    if(s[0]=='?'){
        for(int i=0;i<26;i++) dp[i]=1;
    }
    else dp[s[0]-'a']=1;
    for(int i=1;i<s.size();i++){
        int sum=0,dp2[101]={0};
        for(int j=0;j<26;j++) sum=(sum+dp[j])%mod;
        if(s[i]=='?'){
            for(int j=0;j<26;j++) dp2[j]=(sum-dp[j]+mod)%mod;
        }
        else dp2[s[i]-'a']=(sum-dp[s[i]-'a']+mod)%mod;
        for(int j=0;j<26;j++) dp[j]=dp2[j];
    }
    int ans=0;
    for(int i=0;i<26;i++) ans=(ans+dp[i])%mod;
    return ans;
}
signed main()
{
    cin>>n>>a>>b;
    for(int i=0;i<n;i++){
        if(b[i]=='?') q++;
    }
    for(int i=0;i<n;i++){
        if(i%2==0) od+=b[i];
        else ev+=b[i];
    }
    for(int i=0;i<n;i++){
        if(b[i]!='?'&&b[i]!=a[i]){
            flag=false;
            break;
        }
    }
    for(int i=0;i<n-2;i++){
        if(a[i]==a[i+2]){
            rep=true;
            break;
        }
    }
    int ans=(qpow(26,q)-(calc(od)*calc(ev)%mod)+flag-(flag&&rep)+mod)%mod;
    cout<<ans<<"\n";

    return 0;
}