AT_agc025_b RGB Coloring 题解

Problem

Solution

由于涂绿色的得分为 \(A+B\)，所以可以将红色与蓝色独立考虑。

依次枚举红色的个数，假定为 \(i\)，所以剩余需要的得分为 \(K-i\times A\)，判断是否能被 \(B\) 整除，若能，则蓝色个数为 \(\frac{K-i\times A}{B}\)，设为 \(j\)，则总方案累加 \(C^{i}_{n}\times C^{j}_{n}\)，除法用逆元即可。

Code

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define FOR(i,a,b) for(int i=(a);i>=(b);i--)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long

const int P=998244353,N=3e5+4;
int n,A,B,K,mul[N],ans;
inline int ksm(int b,int p,int k)
{
	int qz=b,sum=1;
	while(p>0)
	{
		if(p&1==1)sum=(sum*qz)%k;
		qz=(qz*qz)%k;
		p>>=1;
	}
	return sum%k;
}
inline int inv(int x){return ksm(x%P,P-2,P);}
inline void init()
{
	mul[0]=1;
	For(i,1,n)mul[i]=(mul[i-1]*i)%P;
}
inline int C(int n,int m)
{
	if(n<0 || m<0 || m>n)return 0;
	return mul[n]*inv(mul[n-m])%P*inv(mul[m])%P;
}
signed main()
{
	IOS;
	cin>>n>>A>>B>>K;
	init();
	For(i,0,n)if((K-i*A)%B==0)ans=(ans+C(n,i)*C(n,(K-i*A)/B)%P)%P;
	cout<<ans;

	return 0;
}