清明雨上题解

Misty-Hazers 2023-12-27 10:10:22 2024-02-19 12:28:17 2 返回题目

感觉cls做法有点复杂,再写一份(

题意:给定 , ,求合法的 数量使得 + + =

我们会发现,当 时是好做的,即插板法,合法方案数为

那么我们可以考虑容斥,减去 存在单个x 满足 存在两个x 满足 的即可。

但我们会发现,减第一个时会减两遍第二种的情况,所以我们第二遍要加回第二种的方案数。

细节很少。

只放核心代码:

i128 k, s;
k = read(); s = read();

i128 ans = (s + 2) * (s + 1) / 2;
//初始方案

auto f = [&](i128 p) -> i128 {
	// choose x + y <= p
	if (p < 0) {
		return 0;
	}
	return (p + 1) * (p + 2) / 2;
};

ans -= f(s - (k + 1)) * 3;
// 减第一种情况
ans += f(s - 2 * (k + 1)) * 3;
// 要加回第二种情况

write(ans);
std::cout << std::endl;
{{ vote && vote.total.up }}