Atcoder Grand Contest 019 F - Yes or No(贪心+组合数学)

MARK on 2022.1.3:由于本人觉得“组合数学杂题选做”这篇博客太累赘了,故将其删除并将其中所有题解都单独开一篇博客写入。

题面传送门

首先我们贪心地想,如果现在 Yes 个数多于 No 的个数那我们肯定会猜 Yes,如果 No 个数多于 Yes 个数那我们肯定会猜 No,否则我们随便猜哪个都无所谓。我们考虑以剩余的答案为 Yes 的问题个数为横坐标,剩余的答案为 No 的问题个数为纵坐标建一个坐标系,那么不难发现一次猜答案的过程可以描述为一条 \((n,m)\to(0,0)\)​ 的路径,手玩一下可以发现只要你按照最优策略猜总能猜对 \(\max(n,m)\)​ 个,这个容易归纳证明。而你每经过一次对角线都有 \(\dfrac{1}{2}\)​ 的概率猜对,因此一条路径对应的期望猜对次数就是 \(\max(n,m)+\dfrac{1}{2}\text{经过对角线上元素的次数}\)​。前者是个常数可以忽略,而后者可以考虑转换贡献体,枚举对角线上的元素,算出它会被多少个路径经过,然后除以总路径条数。即 \(\sum\limits_{i=1}^{\min(n,m)}\dbinom{2i}{i}·\dbinom{n-i+m-i}{n-i}·\dfrac{1}{\dbinom{n+m}{n}}·\dfrac{1}{2}\)​,直接计算即可。

时间复杂度线性。

const int MAXN = 1e6;
const int MOD = 998244353;
const int INV2 = 499122177;
int qpow(int x, int e) {
	int ret = 1;
	for (; e; e >>= 1, x = 1ll * x * x % MOD)
		if (e & 1) ret = 1ll * ret * x % MOD;
	return ret;
}
int n, m, fac[MAXN + 5], ifac[MAXN + 5];
void init_fac(int n) {
	for (int i = (fac[0] = ifac[0] = ifac[1] = 1) + 1; i <= n; i++)
		ifac[i] = 1ll * ifac[MOD % i] * (MOD - MOD / i) % MOD;
	for (int i = 1; i <= n; i++) {
		fac[i] = 1ll * fac[i - 1] * i % MOD;
		ifac[i] = 1ll * ifac[i - 1] * ifac[i] % MOD;
	}
}
int binom(int n, int k) {return 1ll * fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;}
int main() {
	init_fac(MAXN); scanf("%d%d", &n, &m); int res = 0;
	for (int i = 1; i <= min(n, m); i++) res = (res + 1ll * binom(i + i, i) % MOD * binom(n - i + m - i, n - i)) % MOD;
	res = 1ll * res * qpow(binom(n + m, n), MOD - 2) % MOD * INV2 % MOD;
	printf("%d\n", (res + max(n, m)) % MOD);
	return 0;
}
上一篇:Contest3188 - 2021级新生个人训练赛第42场_G: 4-adjacent


下一篇:a标签中的点击事件