AtCoder AGC058D – Yet Another ABC String – 题解

AGC058D – Yet Another ABC String

将 $\mathtt{A,B,C}$ 换成 $0,1,2$。记 $a,b,c$ 是题面中 $\mathtt{A,B,C}$ 的数量，$n=a+b+c$。我们称位置 $i$ 不合法，当且仅当 $S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3$。将其视为两条边 $(i-2,i-1),(i-1,i)$，那么所有不合法的位置造成的连边将会形成若干条链。

考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 $(-1)^c$，$c$ 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 $f(l,0)$ 表示“大小为偶数，且能够连成长度恰为 $l$ 的链”的非法位置集合数量；$f(l,1)$ 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 $(l_1,l_2,\cdots,l_s)$（此处的“链”长度均不小于 $3$），答案即为
$$\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right)$$

易得有 $f(l,b)=f(l-1,\lnot b)+f(l-2,\lnot b)$。设 $g(l)=-f(l,1)+f(l,0)$，边界为 $g(1)=g(2)=0,g(3)=-f(3,1)=-1$。我们惊奇地发现
$$\forall x>2,g(l)=\begin{cases}-1,&l\equiv 0\pmod 3\\1,&l\equiv 1\pmod 3\\0&l\equiv 2\pmod 3\end{cases}$$
这也就意味着，只需考虑所有 $l_i=3k_i+b_i\ (k_i>0,b_i\in\{0,1\})$！

于是我们考虑怎样快速计算染色方案数。对于 $l_i=3k_i$，总是分别消耗 $k_i$ 个 $0,1,2$；对于 $l_i=3k_i+1$，它的方案由最后一个元素唯一决定，同时除它以外每种颜色亦使用 $k_i$ 个。未钦定的位置则可任意填写。那么，令某种划分为 $(l_1,\cdots,l_s)$，且有 $\sum_{i=1}^s[b_i=0]=t_0$，则每种颜色各无条件使用了 $t=\sum_{i=1}^sk_i$ 个；将 $l_i=3k_i+1$ 的末尾元素和所有未钦定元素一同考虑，附上容斥系数 $g(l_i)$，则本划分的最终贡献为 $\underline{\binom{a+b+c-3t}{a-t,b-t,c-t}}(-3)^{t_0}$。

故而我们枚举 $t$、枚举 $s$（则要把 $t$ 个“$3$”非空地分配到 $s$ 个 $l_i$ 中）、枚举 $t_0$（则有 $s-t_0$ 个 $l_i=3k_i+1$），在上文基础上再考虑这 $s$ 条链在全串中的位置和相对顺序，答案即为
$$\begin{aligned}
&\sum_{t=0}^{\min\{a,b,c\}}\sum_{s=0}^t\sum_{t_0=0}^s\binom{n-3t-(s-t_0)+t_0}{s}\binom{s}{t_0}\binom{t-1}{s-1}\binom{n-3t}{a-t,b-t,c-t}(-3)^{t_0}\\
=&\sum_{t=0}^{\min\{a,b,c\}}\binom{n-3t}{a-t,b-t,c-t}\sum_{s=0}^t\binom{t-1}{s-1}\sum_{t_0=0}^{s}\binom{n-3t+t_0}{s}\binom{s}{t_0}(-3)^{t_0}\\
=&\sum_{t=0}^{\min\{a,b,c\}}\binom{n-3t}{a-t,b-t,c-t}\sum_{s=0}^t\binom{t-1}{s-1}\sum_{t_0=0}^s\binom{n-3t+t_0}{t_0}\binom{n-3t}{s-t_0}(-3)^{t_0}\\
=&\sum_{t=0}^{\min\{a,b,c\}}\binom{n-3t}{a-t,b-t,c-t}\sum_{t_0=0}^t\binom{n-3t+t_0}{t_0}(-3)^{t_0}\boxed{\sum_{s=t_0}^{t}\binom{t-1}{s-1}\binom{n-3t}{s-t_0}}
\end{aligned}$$

尝试化简最右侧求和号。由范德蒙德卷积，可得
$$\sum_{x}\binom{p}{x+u}\binom{q}{x+v}=\binom{p+q}{p+v-u}$$
带入得方框内式子等于 $\dbinom{n-2t-1}{n-3t+t_0-1}$。现在尝试化简关于 $t_0$ 的求和。不妨将其化作以下式子：
$$\begin{aligned}
&\sum_{x}\binom{p+x}{x}(-3)^x\binom{r-1}{p+x-1}\\
=&\sum_x\binom{p+x}{p}\binom{r}{p+x}\frac{p+x}{r}(-3)^x\\
=&\sum_x\binom{r}{p}\binom{r-p}{x}\frac{p+x}{r}(-3)^x\\
=&\frac{1}{r}\binom{r}{p}\sum_x\binom{r-p}{x}(p+x)(-3)^x\\
=&\frac{1}{r}\binom{r}{p}\left(p\left(\sum_x\binom{r-p}{x}(-3)^x\right)+\left(\sum_x\binom{r-p}{x}x(-3)^x\right)\right)\\
=&\frac{1}{r}\binom{r}{p}\left(p(-2)^{r-p}-3(r-p)(-2)^{r-p-1}\right)
\end{aligned}$$

代入 $p=n-3t,r=n-2t$，即刻得到答案为
$$\sum_{t=0}^{\min\{a,b,c\}}\binom{n-3t}{a-t,b-t,c-t}(n-3t)\binom{n-2t-1}{n-3t-1}(-2)^t\frac{2n-3t}{2}$$

时间复杂度 $\operatorname{O}(n)$，常数大。

Submission #37286307

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
#include <bits/stdc++.h>
using namespace std;

#define inl __always_inline
using ll = long long;

constexpr int N = 3e6 + 10, P = 998244353, inv2 = P+1>>1;
int a, b, c, lmt, n; ll fact[N], finv[N], ans;

inl ll fpow (ll a, ll b, int mod = P) {
	ll res = 1; a %= mod;
	for (; b; b >>= 1) {
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
	}
	return res;
}
inl void calc_inv (int n) {
	fact[0] = 1;
	for (int x = 1; x <= n; ++x)
		fact[x] = fact[x-1] * x % P;
	finv[n] = fpow (fact[n], P - 2);
	for (int x = n - 1; ~x; --x)
		finv[x] = finv[x+1] * (x + 1) % P;
}
inl ll C (int x, int y) { return x < y || y < 0
	? x == -1 && y == -1 ? 1 : 0
	: fact[x] * finv[y] % P * finv[x-y] % P; }

int main () {
	/*  */
	scanf ("%d%d%d", &a, &b, &c);
	calc_inv (n = a + b + c);
	lmt = min ({ a, b, c });
	for (ll t = 0, powm2 = 1; t <= lmt; ++t, (powm2 *= P-2) %= P)
		ans += fact[n-2*t-1] * powm2 % P * (2*n-3*t) % P
			* finv[t] % P * inv2 % P * finv[a-t] % P * finv[b-t] % P * finv[c-t] % P;
	printf ("%lld", ans % P);

	return 0;
}