526互联

AtCoder Grand Contest 058 D Yet Another ABC String

发布时间 2023-07-08 11:01:42作者: zltzlt

洛谷传送门

AtCoder 传送门

Orz H6_6Q，感谢他给我们带来了这道容斥好题。

这个东西看起来很不好搞。可以尝试容斥。

但是我们要容斥啥？钦定 ABC 不出现，其他任意？感觉还是很难算。

观察不合法子串，发现它们很有特点。如果我们钦定 \(\texttt{A}\) 为 \(0\)，\(\texttt{B}\) 为 \(1\)，\(\texttt{C}\) 为 \(2\)，那么不合法串相当于 \(S_i + 1 \equiv S_{i + 1} \pmod 3\)。

并且我们还发现一个性质，如果 \(S_{i \sim i + 2}\) 不合法，即 \(S_{i \sim i + 2}\) 为 \(\texttt{ABC}, \texttt{BCA}, \texttt{CAB}\) 中的其中一个，并且 \(S_{i + 1 \sim i + 3}\) 也不合法，那么 \(S_{i \sim i + 3}\) 也不合法。因为由上面不合法子串的特点我们得到了这个东西具有传递性。

现在我们尝试考虑每个极长不合法子串。发现它们既有起点又有终点。我们尝试容斥起点。即我们钦定有 \(i\) 个极长不合法子串的起点。

极长不合法子串的长度还不确定，但是我们发现只要钦定它们的长度 \(\ge 3\)，即每个字母至少出现一次即可。

于是我们现在相当于有 \(a - i\) 个 \(\texttt{A}\)，\(b - i\) 个 \(\texttt{B}\)，\(c - i\) 个 \(\texttt{C}\) 是自由的。我们需要把它排成一个初始串。这部分的方案数由多重组合数易得为 \(\frac{(a + b + c - 3i)!}{(a - i)! (b - i)! (c - i)!}\)。

然后，我们需要把 \(i\) 个串，每个都是 \(\texttt{ABC}, \texttt{BCA}, \texttt{CAB}\) 中之一的串插入一开始排成的那个初始串。如果插入的位置在开头，那么 \(3\) 个串都可以被选择插入；如果在中间，因为我们容斥的是极长不合法子串的起点，也就是说它们必须是起点，其他的可以是也可以不是，所以我们不能接在字母序上一个字母后面，导致这个字母成为了起点。具体一点就是，\(\texttt{ABC}\) 不能接在 \(\texttt{C}\) 后面，\(\texttt{BCA}\) 不能接在 \(\texttt{A}\) 后面，\(\texttt{CAB}\) 不能接在 \(\texttt{B}\) 后面。我们发现无论插入位置前一个字母是什么，插入的串都有 \(2\) 种选择。

现在考虑统计插入初始串并选择是 \(\texttt{ABC}, \texttt{BCA}\) 还是 \(\texttt{CAB}\) 的方案数。分类讨论。

  • 如果没有串被放到开头，那么初始串有 \(a + b + c - 3i\) 个空隙。我们需要把 \(i\) 个起点分配成 \(a + b + c - 3i\) 份，每份可以为空，然后再按份对应地插入到这么多空隙中，再乘上选择插入的是哪个串的方案数。于是这部分的方案数就是 \(\binom{i + a + b + c - 3i - 1}{a + b + c - 3i - 1} \times 2^i\)。
  • 如果有 \(1\) 个串被放到开头，那么我们先放一个起点到开头，那么现在的串有 \(a + b + c + 3i + 1\) 个空隙，并且我们还剩 \(i - 1\) 个起点。由上面的推法可得这部分的方案数为 \(\binom{i - 1 + a + b + c - 3i}{a + b + c - 3i} \times 2^{i - 1} \times 3\)。

然后，我们把排成初始串的方案数，和上面统计的插入并选择的方案数相乘，再乘上容斥系数 \((-1)^i\)。对于每个 \(i \in [0, \min(a, b, c)]\) 求和，即是答案。

启发：容斥的东西可以是非常规的，不一定是题目直接给出的东西。

code 
// Problem: D - Yet Another ABC String
// Contest: AtCoder - AtCoder Grand Contest 058
// URL: https://atcoder.jp/contests/agc058/tasks/agc058_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;

/*
很强的容斥！

考虑一个极长的不合法子串连续段 `ABCABC...`，我们考虑容斥**每个连续段的起点**。

设钦定了 $x$ 个位置**是起点**，其他位置**随意**。对于一个起点的插入，要满足**它前面的字符不是它的前一位**。例如如果要插入 `ABC`，它前一位不能是 `C`，否则起点就要往前移。
*/

const int maxn = 5000100;
const int N = 5000000;
const ll mod = 998244353;

inline ll qpow(ll b, ll p) {
	ll res = 1;
	while (p) {
		if (p & 1) {
			res = res * b % mod;
		}
		b = b * b % mod;
		p >>= 1;
	}
	return res;
}

ll a, b, c, fac[maxn], ifac[maxn], pw[maxn];

inline void init() {
	fac[0] = pw[0] = 1;
	for (int i = 1; i <= N; ++i) {
		fac[i] = fac[i - 1] * i % mod;
		pw[i] = pw[i - 1] * 2 % mod;
	}
	ifac[N] = qpow(fac[N], mod - 2);
	for (int i = N - 1; ~i; --i) {
		ifac[i] = ifac[i + 1] * (i + 1) % mod;
	}
}

inline ll C(ll n, ll m) {
	if (n < m || n < 0 || m < 0) {
		return 0;
	} else {
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}
}

void solve() {
	scanf("%lld%lld%lld", &a, &b, &c);
	ll ans = 0;
	for (int i = 0; i <= min({a, b, c}); ++i) {
		ll t = fac[a + b + c - i * 3] * ifac[a - i] % mod * ifac[b - i] % mod * ifac[c - i] % mod;
		ll res = C(i + a + b + c - i * 3 - 1, a + b + c - i * 3 - 1) * pw[i] % mod;
		if (i) {
			res = (res + C(i - 1 + a + b + c - i * 3, a + b + c - i * 3) * pw[i - 1] % mod * 3 % mod) % mod;
		}
		ans = (ans + ((i & 1) ? mod - 1 : 1) * res % mod * t % mod) % mod;
	}
	printf("%lld\n", ans);
}

int main() {
	init();
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}