「Wdcfr-1」CONsecutive and CONcat (easy ver.) 题解

· · 题解

原来的官方题解比较有误导性，包括但不限于公式中代表变量的字母写错，计算方式很容易让人理解错意思导致边界条件处理不清楚。这里提供一份较为完整且附带参考代码的题解。

考虑把贡献分成两部分：

一部分为单个字符串内部贡献，即对于单个字符串内所有长度为 k 的、由同一个字符组成的子串，每个都会在所有 n! 种方案中出现。每个字符串循环模拟一遍即可，具体地，对于一个极长的、由同一个字符组成、长度为 t(t\ge k) 的子串，其贡献为 n!(t-k+1)。

比较复杂的另一部分是对于两个字符串，前者后缀拼接后者前缀产生的贡献（这里的后缀内的所有字符、缀前内的所有字符都相同）。具体地，因为 m\le 100，所以可以直接枚举后（前）缀的字符、后缀长度与前缀长度然后计算。但是这里如果你直接按官方题解的公式计算，会算重。具体地，设拼接的后缀长度为 s，前缀长度为 p，一种情况就是当 k\le s 或者 k\le p 时，其中有若干长度为 k 的子串在同一个字符串中！

所以我们只能考虑子串跨越两个字符串的情况，及它的真前缀在前者的后缀内，它的真后缀在后者的前缀内。于是我们可以的出后缀长度为 s，前缀长度为 p 时单次产生的贡献，即为 \min\{s,s+p-k+1\}-\max\{s-k+2,1\}+1（证明可自行推导，分别考虑子串左右端点的最小值和最大值并取上交集即可）。又由于在 n! 种情况中特定的两个字符串相邻的情况共有 (n-1)! 种，所以贡献要乘以 (n-1)!。

当然要注意误把同一个字符串“自己和自己拼接”加入贡献的情况，把这部分去掉即可。

把两部分合起来就是最终答案。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353;
main(){
  ios::sync_with_stdio(false);
  int n,m,k,r=0,F=1,F2=1; cin>>n>>m>>k;
  for(int i=2;i<=n;i++)(F*=i)%=p;
  for(int i=2;i<n;i++)(F2*=i)%=p;
  // 预处理阶乘，F = n!，F2 = (n - 1)!
  vector<string> a(n);
  vector<array<int,26> > b(m),s(m);
  // b[i][j] 统计具有长度为 i、字符全部为 c 的极长前缀的字符串个数
  // s[i][j] 类似，只是把前缀换成后缀
  vector e(m,vector<array<int,26> >(m));
  for(auto &i:a){
    cin>>i; int t=0,l=0;
    for(int j=0;j<m;j++)
      if(!j||i[j]==i[j-1])t++; // 与上一个字符相同
      else{
        if(t>=k)(r+=F*(t-k+1)%p)%=p; // 第一部分贡献
        t=1; // 将答案清空，计算下一段
      }
    if(t>=k)(r+=F*(t-k+1)%p)%=p; // 最后还有一段
    for(int j=0;j<m&&i[j]==i[0];j++)l++;
    b[l][i[0]-97]++,s[t][i[m-1]-97]++;
    // l 为极长的、字符相同的前缀长度
    // 利用剩余的 t 得到极长的、字符相同的后缀长度
    // 统计特定字符的前缀、后缀长度确定时的字符串个数
    if(i[0]==i[m-1])e[l][t][i[0]-97]++;
    // 自己和自己拼接的情况
  }
  auto f=[&](int i,int j,int k){
    return min(i,i+j-k+1)-max(1ll,i-k+2)+1;
  }; // 计算拼接时“跨越”字符串的子串数
  // i 为后缀长度，j 为前缀长度
  for(int c=0;c<26;c++)
    for(int i=1;i<m;i++)
      for(int j=max(k-i,1ll);j<m;j++)
        (r+=(b[j][c]*s[i][c]%p-e[j][i][c]+p)%p*f(i,j,k)%p*F2%p)%=p;
         // 统计所有方案数
  cout<<r<<endl;
  return 0;
}