自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:34:30，当前版本为作者最后更新于2024-02-11 11:50:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

考虑把贡献分成两部分：

一部分为单个字符串内部贡献，即对于单个字符串内所有长度为 $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;
}