AGC025B

标签：AGC025B int res d% 1ll fac mod

寄，这都没看出来（

考虑把涂绿色看成同时涂上红色和蓝色，显然这是等效的。

这样红色和蓝色就独立了，枚举红色的个数即可。

时间复杂度 \(\mathcal O(n)\)。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300005, mod = 998244353;
int n, a, b;
ll K;
int fac[N], inv[N];

int qpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod;
		y >>= 1;
	}
	return res;
}

void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = qpow(fac[n], mod - 2);
	for (int i = n - 1; ~i; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

int C(int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return 1ll * fac[n] * inv[n - m] % mod * inv[m] % mod;
}

void add(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}

int main() {
	scanf("%d%d%d%lld", &n, &a, &b, &K);
	init(n);
	int ans = 0;
	for (int i = 0; i <= n; ++i) {
		ll tmp = K - 1ll * i * a;
		if (tmp < 0) break;
		if (tmp % b == 0) add(ans, 1ll * C(n, i) * C(n, tmp / b) % mod);
	}
	printf("%d", ans);
	return 0;
}

标签：AGC025B,int,res,d%,1ll,fac,mod
From： https://www.cnblogs.com/Kobe303/p/16862202.html