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;
}
标签:Coloring,return,int,题解,inv,qz,RGB,inline,mul
From: https://www.cnblogs.com/Wu-ZH/p/18361914