题解P17236【STA - R10 刷墙墙刷】

· · 题解

思路

若不对 a 进行操作，则合法条件为 a=b。

于是我们重点考虑对 a 进行操作的答案。容易发现，对 a 进行有限次操作后得到的字符串 c 必然是存在 i\in[0,n-2)（下标从 0 开始），使得 c_i=c_{i+2}，其余位置任意字符均可。原因很简单。首先我们每次操作肯定是选择长度为 3 的子串，因为选择更长的子串明显会有更多的限制。其次每次操作都可以永久设定两个位置的字符值，即长度为 3 的子串的中间位置和两边任选一个位置，这样所有位置都能任取了，只有最后一次操作的子串 [i,i+2] 需要满足 c_i=c_{i+2}。

于是我们可以想到分奇数位和偶数位进行计数，分别提取 a 和 b 的奇数位和偶数位组成新字符串，统计 b 偶数位和奇数位为 ? 的个数 cnt_0 和 cnt_1，那么根据乘法原理，总情况数（即不论合不合法的答案）就分别为 ans_{01}=26^{cnt_0} 和 ans_{11}=26^{cnt_1}，整体总情况数就为 ans_{01}\cdot ans_{11}。设偶数位和奇数位不合法的情况数分别为 ans_{02} 和 ans_{12}，则整体不合法的情况数为 ans_{02}\cdot ans_{12}，答案为 ans_{01}\cdot ans_{11}-ans_{02}\cdot ans_{12}。

但这还没完，我们还要考虑不操作时的 1 是否要加到答案里。a=b 的前提是 b 已经确定的位置与 a 相同，但能否加到答案里的条件不只是这个，它还得是按操作的标准不合法的，否则会和之前的答案重复计数。那么如何判定不合法呢？只需要判断是否存在 i\in[0,n-2)，使得 a_i=a_{i+2}，如果不存在那么就是不合法的，在满足能使 a=b 的前提下可以加到答案里。

于是重点放在了如何分别统计偶数位和奇数位不合法的情况数。会发现直接用计数原理去想很难算，于是我们想到计数的两大利器“暴搜”和“动态规划”。这里我们用动态规划解决。设 f_{i,j} 为从第 0 位到第 i 位以字符 j 结尾不合法的情况数，由于不合法指不存在 i\in[0,n-2)，使得 c_i=c_{i+2}，于是有状态转移方程 f_{i,j}=\sum_{c\in\Sigma\wedge c\neq j} f_{i-1,c}，当 b_i 为 ? 时可以 j 可以任取，当 b_i 为小写字母时 j 只能取 b_i，最终不合法的情况数就是 \sum_{i\in\Sigma} f_{n-1,i}。直接枚举 i，j，c 转移是 O(n|\Sigma|^2) 的，会爆炸，于是我们可以记 s_i=\sum_{j\in\Sigma} f_{i-1,j}，状态转移方程就转为 f_{i,j}=s_i-f_{i-1,j}，只需要枚举 i，j 进行转移，时间复杂度 O(n|\Sigma|)。当然，这些的前提是不存在 i\in[0,n-2)，使得 b_i，b_{i+2} 均为小写字母且 b_i=b_{i+2}，否则无论问号处取什么字母都是合法的。

总的时间复杂度 O(n|\Sigma|)，瓶颈在于动态规划。

代码

AC Code：（C++11）

#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
#include<numeric>
#include<vector>
#include<set>
#include<queue>
using namespace std;
const int Mod=998244353;
int n,flag1,flag2,ans01,ans02,ans11,ans12,ans;
string a,b,a0,b0,a1,b1;
int power25[1000005],power26[1000005],f[45],g[45];
void solve(string a,string b,int n,int &ans1,int &ans2) {
  int cnt=0;
  for(int i=0;i<n;i++) {
    if(b[i]=='?')
      cnt++;
    else
    if(i>0 && b[i]==b[i-1])
      flag1=0;
    else
    if(a[i]!=b[i])
      flag2=0;
  }
  ans1=power26[cnt]; ans2=0;
  for(int i=0;i<26;i++)
    f[i]=g[i]=0;
  if(b[0]=='?') {
    for(int i=0;i<26;i++)
    f[i]=1;
  }
  else
    f[b[0]-'a']=1;
  for(int i=1;i<n;i++) {
    int s=0;
    for(int j=0;j<26;j++) {
      (s+=f[j])%=Mod;
      g[j]=0;
    }
    if(b[i]=='?') {
      for(int j=0;j<26;j++)
        g[j]=(s-f[j]+Mod)%Mod;
    }
    else
      g[b[i]-'a']=(s-f[b[i]-'a']+Mod)%Mod;
    for(int j=0;j<26;j++)
      f[j]=g[j];
  }
  for(int i=0;i<26;i++)
    (ans2+=f[i])%=Mod;
}
int main() {
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin>>n>>a>>b;
  power25[0]=power26[0]=1;
  for(int i=1;i<=n;i++) {
    power25[i]=(25ll*power25[i-1])%Mod;
    power26[i]=(26ll*power26[i-1])%Mod;
  }
  for(int i=0;i<n;i++)
    if(i%2) {
      a1+=a[i];
      b1+=b[i];
    }
    else {
      a0+=a[i];
      b0+=b[i];
    }
  flag1=flag2=true;
  solve(a0,b0,n-(n>>1),ans01,ans02);
  solve(a1,b1,n>>1,ans11,ans12);
  ans=(1ll*ans01*ans11)%Mod;
  if(flag1) {
    ans=(((ans-1ll*ans02*ans12)%Mod)+Mod)%Mod;
    for(int i=0;i<n-2;i++)
      if(a[i]==a[i+2]) {
        flag2=0;
        break;
      }
    if(flag2) {
      ans++;
      ans%=Mod;
    }
  }
  cout<<ans<<'\n';
}

AC 记录