AtCoder AGC058D – Yet Another ABC String – 题解

AGC058D – Yet Another ABC String

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

考虑容斥。直接钦定指定数量的位置不合法,其方案是难以计算的。又因为容斥系数是 (1)c(-1)^ccc 为钦定的非法位置数量,那么将整个串分成若干个部分分别计算方案,带上容斥系数相乘后累加,结果不变。故而尝试从上文的链入手:易得对于固定长度的一条链,能够连成它的非法位置集合不变。设 f(l,0)f(l,0) 表示“大小为偶数,且能够连成长度恰为 ll 的链”的非法位置集合数量;f(l,1)f(l,1) 则是大小为奇数。染色方案位置集合方案是独立的;则设整个串按顺序被分成了链 (l1,l2,,ls)(l_1,l_2,\cdots,l_s)(此处的“链”长度均不小于 33),答案即为 (l1,,ls)染色方案数((l1,,ls))i=1s((1)f(li,1)+f(li,0))\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(l1,¬b)+f(l2,¬b)f(l,b)=f(l-1,\lnot b)+f(l-2,\lnot b)。设 g(l)=f(l,1)+f(l,0)g(l)=-f(l,1)+f(l,0),边界为 g(1)=g(2)=0,g(3)=f(3,1)=1g(1)=g(2)=0,g(3)=-f(3,1)=-1。我们惊奇地发现 x>2,g(l)={1,l0(mod3)1,l1(mod3)0l2(mod3)\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} 这也就意味着,只需考虑所有 li=3ki+bi (ki>0,bi{0,1})l_i=3k_i+b_i\ (k_i>0,b_i\in\{0,1\})

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

故而我们枚举 tt、枚举 ss(则要把 tt 个“33”非空地分配到 sslil_i 中)、枚举 t0t_0(则有 st0s-t_0li=3ki+1l_i=3k_i+1),在上文基础上再考虑这 ss 条链在全串中的位置和相对顺序,答案即为 t=0min{a,b,c}s=0tt0=0s(n3t(st0)+t0s)(st0)(t1s1)(n3tat,bt,ct)(3)t0=t=0min{a,b,c}(n3tat,bt,ct)s=0t(t1s1)t0=0s(n3t+t0s)(st0)(3)t0=t=0min{a,b,c}(n3tat,bt,ct)s=0t(t1s1)t0=0s(n3t+t0t0)(n3tst0)(3)t0=t=0min{a,b,c}(n3tat,bt,ct)t0=0t(n3t+t0t0)(3)t0s=t0t(t1s1)(n3tst0)\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}

尝试化简最右侧求和号。由范德蒙德卷积,可得 x(px+u)(qx+v)=(p+qp+vu)\sum_{x}\binom{p}{x+u}\binom{q}{x+v}=\binom{p+q}{p+v-u} 带入得方框内式子等于 (n2t1n3t+t01)\dbinom{n-2t-1}{n-3t+t_0-1}。现在尝试化简关于 t0t_0 的求和。不妨将其化作以下式子: x(p+xx)(3)x(r1p+x1)=x(p+xp)(rp+x)p+xr(3)x=x(rp)(rpx)p+xr(3)x=1r(rp)x(rpx)(p+x)(3)x=1r(rp)(p(x(rpx)(3)x)+(x(rpx)x(3)x))=1r(rp)(p(2)rp3(rp)(2)rp1)\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=n3t,r=n2tp=n-3t,r=n-2t,即刻得到答案为 t=0min{a,b,c}(n3tat,bt,ct)(n3t)(n2t1n3t1)(2)t2n3t2\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}

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

Submission #37286307

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 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; }
  • 2022年12月16日