LOJ3123 [CTS2019] 重复

Description

给定小写字母组成的字符串 $s$ 及正整数 $m$，求有多少小写字母组成的字符串 $t$ 满足 $t$ 的无穷重复中存在一个和 $s$ 长度相同但比 $s$ 字典序小的子串。

$|s|,m\leq2000$。

Solution

设 $s=s_{1,n}$，即 $n=|s|$（我们用 $s_{a,b}$ 表示从 $a$ 到 $b$ 的子串）。

首先我们观察到一个性质：

引理 1

如果 $s$ 的某个长为 $t$ 的子串 $s_{i,i+t-1}$ 字典序小于长为 $i$ 的前缀 $s_{1,t}$，那么把 $s$ 替换成 $s_{1,i+t-2}$ ，答案是不变的。

证明也不难：如果 $t$ 的无穷重复中有某个子串 $p<s$，那么要么 $p_{1,i+t-2}<s_{1,i+t-2}$，要么 $p_{1,i+t-2}=s_{1,i+t-2}$ 而 $p_{i+t-1,n}<s_{i+t-1,n}$。

对于前者，显然 $p_{1,i-1}$ 也是 $t$ 的无穷重复的子串；对于后者，可以发现必有 $p_{i+t-1}\leq s_{i+t-1}$，从而 $p_{i,i+t-1}\leq s_{i,i+t-1}<s_{1,t}$，所以从 $p_i$ 这一位开头的字符串字典序一定比 $s_{i+t-2}$ 小。$\square$

举个例子：如果 $s$ 为 egefd，由于 ef 大于 eg，因此如果有一个小于 $s$ 的串在前三位和 $s$ 相等的话第四位必定小于 $s_4$ 也就是小于 f。那这样的话从这个串的第三位开头的串就是 e?*，其中 ?<d<g，因此这个串也一定比 ege 小。

同理我们也可以证明：如果 $s$ 有某个 border，那么可以把这个 border 删去。

我们这样处理过 $s$ 之后，它就满足：$s$ 的任意子串大于等于 $s$ 中与之等长的前缀；$s$ 的任意后缀严格大于与之等长的前缀。称满足第一个条件的串叫做可做串，两个都满足的叫强可做串（因为我只会做这样的串），那么我们要求出 $s$ 的最长可做前缀，并只考虑这个前缀。

至于如何处理，可以求一遍 KMP。假定 $s$ 的长为 $i-1$ 的前缀是强可做的，要求它的长为 $i$ 的前缀是不是可做的。

假设有某个后缀 $s_{t,i}$ 小于等长的前缀 $s_{1,i-t+1}$，那么肯定是 $s_{1,i-t}=s_{t,i-1}$ 而 $s_{i-1+1}>s_i$（因为前面的都是可做的）。也就是说是一个 border 拼上一个字符。

但是因为前面的串是可做的，可以证明 KMP 那种跳最长 border 过程中字符是非升的，所以只需要判 $i-1$ 处的最长 border 即可。这样的话就可以得到最长的可做后缀；然后不停判断是否存在 border，如果存在就删去即可。

现在我们得到了一个可做串 $s$。考虑用 $26^m$ 减去不合法的情况，即从每个位置开始的子串字典序都大于等于 $s$ 的情况。大于等于 $s$ 等价于大于 $pred(s)$（最大的比 $s$ 字典序小的字符串）。

只考虑 $n\leq m$ 的情况（如果 $m>n$，那么只需要看一个前 $m$ 位恰好等于 $s_{1,m}$ 的串的重复是否比 $s$ 小。根据 $s$ 的强可做性，这个是必然的。因此只需要算大于 $s$ 的情况即可，因为等于 $s$ 也是合法的）。

由于 $s$ 的后缀严格大于前缀，即 $s_n>s_1$，其 $pred$ 就是将末尾减一的结果（不需要退位）。可以发现得到的串必定是可做的，即任意子串大于等于等长的前缀。

以下我们设 $s$ 是可做的（就是之前那个 $pred(s)$），且 $n=|s|<m$，求有多少个长度为 $m$ 的串 $t$ 满足 $t$ 的无穷重复的任意长度为 $n$ 的子串都大于 $s$。

$t$ 的无穷重复中任意子串大于 $s$，等价于说把 $t$ 看成一个环之后，其任意长为 $n$ 的子串字典序大于 $s$。下面我们先把 $t$ 看成一个环。称满足条件的环是合法环。

定义一个串 $p$ 是好的，当且仅当 $|p|\leq n$，且 $p_{1,|p|-1}=s_{1,|p|-1}, p_{|p|}>s_{|p|}$。

我们有如下引理：

引理 2

由若干个好串拼接而成的环 $t$ 是合法环。并且对于任何一个合法环，将其表示成好串的拼接的方式是唯一的。

证明：引理有三个部分，我们分别证明：

1. 先证明好串的拼接是合法的。如果有一个好串的拼接，对于其任意一个长为 $n$ 的子串 $q$，$q$ 一定有一个前缀 $q_{1,k}$ 是某个好串的后缀。 设这个好串为 $p$，那么 $q_{1,k}=p_{|p|-k+1,|p|}>s_{|p|-k+1,|p|}\geq s_{1,k}$。其中大于号是因为好串的前面部分和 $s$ 对应部分相等而最后一个字母大于 $s$ 的对应字母， 大于等于号是因为 $s$ 的可做性。于是 $q_{1,k}>s_{1,k}$，显然有 $q>s$。
2. 再证明合法环可以分解成好串的拼接。对于一个合法环，找到其最小表示法 $t$（即，其循环排列中字典序最小者），那么从开头开始对 $s$ 做匹配，每次发现某个位置比 $s$ 的相应位置大的时候划分出一个好串。 只需要证明匹配到末尾的时候不可能还剩下没有匹配完的部分。如果到了末尾还没有匹配完，那么 $t$ 必定有一个后缀与 $s$ 的某个前缀相等（就是匹配剩下的部分）。 设 $t_{|t|-k+1,|t|}=s_{1,k}$，那么必定有 $t_{1,k}=s_{1,k}$，否则的话 $t$ 的某个长度小于等于 $k$ 的前缀是好串，而好串必定比 $s$ 字典序大，这和 $t$ 是最小表示不符； 但是既然 $t_{1,k}=s_{1,k}$，因为 $t$ 实际上首尾是相邻的（是个环），所以 $t_{|t|-k+1,|t|}+t_{1,k}=s_{1,k}+s_{1,k}$ 也是其子串，因此必须要大于等于 $s_{1,2k}$，即 $s_{1,k}\geq s_{k+1,2k}$， 这样的话，根据 $s$ 的可做性又有 $s_{k+1,2k}\geq s_{1,k}$，于是 $s_{1,k}=s_{k+1,2k}$。这样的话必须有 $t_{1,2k}=s_{1,2k}$，因为 $t$ 存在一个与 $s_{1,2k}$ 相等的子串，而 $t$ 是最小表示法从而 $\leq s_{1,2k}$， $t$ 又是合法串因此 $t_{1,2k}\geq s_{1,2k}$。这样的话，重复之前的步骤，可以发现 $s_{1,k}=s_{k+1,2k}=s_{2k+1,3k}=\dots$，而 $t_{1,pk}=s_{1,pk}$。 当 $p$ 充分大的时候，这说明 $s$ 必须无限长，这显然是矛盾的，因此原来的假设（$t$ 最后匹配好串没有匹配完）是不成立的。
3. 最后要证明好串拆分是唯一的。事实上如果固定起点，那么好串划分一定是唯一的，即上面的构造方式；而任选 $t$ 的某个最小表示法，根据上面的证明容易发现不可能存在跨越首尾的好串，于是可以直接从这个点开始划分。

这样，我们就完成了引理的证明。$\square$

这样的话，相当于对好串的拼接方式计数。显然对于某个长度，这个长度的好串个数是容易计算的（就是 ‘z’ 减去 $s_i$），那么设 $a_i$ 表示长为 $i$ 的好串个数，$f_i$ 表示好串排成一排长度和为 $i$ 的方案数，显然有

$f_i=\sum_{j=1}^{\min(i,n)}a_jf_{i-j}$

统计答案时，如果没有跨越首尾的好串，方案数就是 $f_m$；否则枚举跨越首尾的好串长度 $i$，方案数就是 $(i-1)a_if_{m-i}$。

可以在 $O(nm)$ 或者 $O(n+m\log m)$（多项式求逆）或者 $O(n^2\log m)$（常系数递推）或者 $O(n\log n\log m)$（多项式取模优化常系数递推）来求解。

下面是 $O(n+m\log m)$ 的做法。NTT 板子是从论文哥那里抄的。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>

typedef long long LL;
typedef unsigned long long ULL;
const int mod = 998244353;
const int N = 200050;

LL pow_mod(LL a, LL b) {
  LL ans = 1;
  for (; b; b >>= 1, a = a * a % mod)
    if (b & 1) ans = ans * a % mod;
  return ans;
}

int L, rev[N];
LL w[N];

void InitDFT(int n) {
  L = 1;
  while (L <= n) L <<= 1;
  for (int i = 1; i < L; ++i)
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * L / 2);
  LL g = pow_mod(3, (mod - 1) / L);
  w[L >> 1] = 1;
  for (int i = L >> 1; i + 1 < L; ++i)
    w[i + 1] = w[i] * g % mod;
  for (int i = (L >> 1) - 1; i > 0; --i)
    w[i] = w[i << 1];
}

void DFT(LL *A, int len) {
  static ULL T[N];
  int k = 0, t = len;
  while (t < L) t <<= 1, ++k;
  for (int i = 0; i < len; ++i)
    T[rev[i] >> k] = (A[i] + mod) % mod;
  for (int h = 1; h < len; h <<= 1)
    for (int i = 0; i < len; i += (h << 1))
      for (int j = 0; j < h; ++j) {
        ULL qaq = T[i + j + h] * w[h + j] % mod;
        T[i + j + h] = (T[i + j] + mod - qaq) % mod;
        T[i + j] = (T[i + j] + qaq) % mod;
      }
  for (int i = 0; i < len; ++i)
    A[i] = T[i] % mod;
}

void IDFT(LL *A, int len) {
  std::reverse(A + 1, A + len);
  DFT(A, len); LL v = -(mod - 1) / len;
  for (int i = 0; i < len; ++i)
    A[i] = A[i] * v % mod;
}

inline int getLen(int t) { return 1 << (32 - __builtin_clz(t)); }

void INV(const LL *A, int n, LL *B) {
  if (n == 1) return void(B[0] = pow_mod(A[0], mod - 2));
  int m = (n + 1) / 2;
  INV(A, m, B);

  static LL t1[N], t2[N];
  int l = getLen(n + n);
  for (int i = 0; i < n; ++i) t1[i] = A[i];
  for (int i = n; i < l; ++i) t1[i] = 0;
  for (int i = 0; i < m; ++i) t2[i] = B[i];
  for (int i = m; i < l; ++i) t2[i] = 0;

  DFT(t1, l); DFT(t2, l);
  for (int i = 0; i < l; ++i)
    t1[i] = t2[i] * (2 - t1[i] * t2[i] % mod) % mod;
  IDFT(t1, l);

  for (int i = m; i < n; ++i) B[i] = t1[i];
}

char s[N];
int n, m, nxt[N];
LL A[N], B[N];

int main() {
  scanf("%d%s", &m, s);
  n = strlen(s);
  nxt[0] = nxt[1] = 0;
  for (int i = 1, j = 0; i < n; ++i) {
    while (j && s[j] != s[i]) j = nxt[j];
    nxt[i + 1] = j += s[j] == s[i];
  }
  for (int i = 1; i < n; ++i) if (s[i] < s[nxt[i]]) n = i;
  while (nxt[n]) --n;
  if (n > m) ++s[(n = m) - 1];
  --s[n - 1];
  A[0] = 1;
  for (int i = 1; i <= n; ++i) A[i] = s[i - 1] - 'z';
  InitDFT((m + 1) * 2);
  INV(A, m + 1, B);
  LL ans = (pow_mod(26, m) - B[m]) % mod;
  for (int i = 2; i <= n; ++i)
    ans = (ans + (i - 1) * A[i] * B[m - i]) % mod;
  printf("%lld\n", (ans + mod) % mod);
}