_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

LOJ3123 [CTS2019] 重复

Description

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

s,m2000|s|,m\leq2000

Solution

s=s1,ns=s_{1,n},即 n=sn=|s|(我们用 sa,bs_{a,b} 表示从 aabb 的子串)。

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

引理 1

如果 ss 的某个长为 tt 的子串 si,i+t1s_{i,i+t-1} 字典序小于长为 ii 的前缀 s1,ts_{1,t},那么把 ss 替换成 s1,i+t2s_{1,i+t-2} ,答案是不变的。

证明也不难:如果 tt 的无穷重复中有某个子串 p<sp<s,那么要么 p1,i+t2<s1,i+t2p_{1,i+t-2}<s_{1,i+t-2},要么 p1,i+t2=s1,i+t2p_{1,i+t-2}=s_{1,i+t-2}pi+t1,n<si+t1,np_{i+t-1,n}<s_{i+t-1,n}

对于前者,显然 p1,i1p_{1,i-1} 也是 tt 的无穷重复的子串;对于后者,可以发现必有 pi+t1si+t1p_{i+t-1}\leq s_{i+t-1},从而 pi,i+t1si,i+t1<s1,tp_{i,i+t-1}\leq s_{i,i+t-1}<s_{1,t},所以从 pip_i 这一位开头的字符串字典序一定比 si+t2s_{i+t-2} 小。\square

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

同理我们也可以证明:如果 ss 有某个 border,那么可以把这个 border 删去。

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

至于如何处理,可以求一遍 KMP。假定 ss 的长为 i1i-1 的前缀是强可做的,要求它的长为 ii 的前缀是不是可做的。

假设有某个后缀 st,is_{t,i} 小于等长的前缀 s1,it+1s_{1,i-t+1},那么肯定是 s1,it=st,i1s_{1,i-t}=s_{t,i-1}si1+1>sis_{i-1+1}>s_i(因为前面的都是可做的)。也就是说是一个 border 拼上一个字符。

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

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

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

由于 ss 的后缀严格大于前缀,即 sn>s1s_n>s_1,其 predpred 就是将末尾减一的结果(不需要退位)。可以发现得到的串必定是可做的,即任意子串大于等于等长的前缀。

以下我们设 ss 是可做的(就是之前那个 pred(s)pred(s)),且 n=s<mn=|s|<m,求有多少个长度为 mm 的串 tt 满足 tt 的无穷重复的任意长度为 nn 的子串都大于 ss

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

定义一个串 pp 是好的,当且仅当 pn|p|\leq n,且 p1,p1=s1,p1,pp>spp_{1,|p|-1}=s_{1,|p|-1}, p_{|p|}>s_{|p|}

我们有如下引理:

引理 2

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

证明:引理有三个部分,我们分别证明:

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

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

这样的话,相当于对好串的拼接方式计数。显然对于某个长度,这个长度的好串个数是容易计算的(就是 ‘z’ 减去 sis_i),那么设 aia_i 表示长为 ii 的好串个数,fif_i 表示好串排成一排长度和为 ii 的方案数,显然有

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

统计答案时,如果没有跨越首尾的好串,方案数就是 fmf_m;否则枚举跨越首尾的好串长度 ii,方案数就是 (i1)aifmi(i-1)a_if_{m-i}

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#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);
}