Submission #3784115

---

Source Code Expand

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const ll mod = 998244353;
const ll N = 3 * 100000 + 5;
ll Mode(ll a, ll b){
	ll sum = 1;
	while (b) {
		if (b & 1) {
			sum = (sum * a) % mod;
			b--;
		}
		b /= 2;
		a = a * a % mod;
	}
	return sum;
}
//快速幂取模 

ll inv(ll a){
	return Mode(a, mod - 2);
}
//逆元 

ll jc[N];
void init() //预处理算阶乘
{
    jc[0] = 1;
    for(int i = 1; i < N; ++i)
    jc[i] = jc[i-1]*i%mod;
}
ll C(ll n, ll m){
    if(n<0||m>n)
        return 0;
    return ((jc[n] % mod) * ((inv(jc[m]) * inv(jc[n - m])) % mod)) % mod;
}//组合数 
int main(){
//	ios::sync_with_stdio(false);
//	ifstream cin("data.txt");
//	freopen("data.txt", "r", stdin);
	init();
	ll n, a, b, k;
	ll ans = 0;
	cin >> n >> a >> b >> k;
	if(k == 0){
		cout << 1 << endl;
		return 0;
	}
	for(ll i = 1; i <= n; i++){
		//cout << "n = " << i << endl;
		if(!((k - a * i) % b)){
			//cout << "jin\n";
			ll t1 = i;
			ll t2 = ((k - a * i) / b); 
			//cout << "t1 = " << t1 << "\nt2 = " << t2 << endl;
			for(ll z = 0; z <= min(t1, t2); z++){
				//cout << "z = " << z << endl;
				ll x = t1 - z;//cout << "x = " << x << endl;
				ll y = t2 - z;//cout << "y = " << y << endl;
				ll m = n - z - x - y;//cout << "m = " << m << endl;
				if(x < 0 || y <0 || m < 0)continue;
				ll cnt = C(n, x) % mod;
				cnt *= C(n - x, y);
				cnt %= mod;
				cnt *= C(n - x - y, z);
				cnt %= mod;
				cnt *= C(n - x - y - z, m);
				cnt %= mod;
				//cout << "cnt = " << cnt << endl;
				ans += cnt;
				ans %= mod;
			}
		}
	}
	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result