Submission #3018171

---

Source Code Expand

#include<iostream>

#include <vector>
#include <list>
#include<stack>
#include<queue>
#include<array>

#include <set>
#include<map>

#include<string>
#include<stdlib.h>

#include<algorithm>
#include <functional>
#include<math.h>

#include<fstream>
#include<iomanip>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;

#define FOR(k,m,n) for(ll (k)=(m);(k)<(n);(k)++)
#define REP(i,n) FOR((i),0,(n))
#define WAITING(str) int str;std::cin>>str;
#define DEBUGING(str) cout<<str<<endl

constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 998244353;// 10^9+7
constexpr ll LIM = 400'000;

//変数
ll N, A, B, K;




//繰り返し累乗法
//in:  x,n,mod
//out: x^n(Mod mod)
template<typename T>
T mod_pow(T x, T n, T mod) {
	T res = 1;
	while (n > 0) {
		if (n & 1)res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}

//
vector<ll> fact, inv;
void make_contents()
{
	ll tmp = 1;
	fact.push_back(0);
	FOR(i, 1, LIM) {
		tmp *= i;
		tmp %= MOD;
		fact.push_back(tmp);
	}

	tmp = mod_pow(tmp, MOD - 2, MOD);
	//inv.push_back(tmp);
	for (ll i = LIM - 1; i > 0; i--) {
		tmp *= i;
		tmp %= MOD;
		inv.push_back(tmp);
	}
	reverse(inv.begin(), inv.end());
	fact[0] = inv[0] = 1;
	/*正当性確認
	REP(i, LIM) {
	cerr << (fact[i] * inv[i]) % MOD << endl;
	}
	*/
}

ll comb(ll n, ll k) {
	ll res = fact[n];
	res *= inv[k]; res %= MOD;
	res *= inv[n - k]; res %= MOD;
	return res;
}





//サブ関数
//入力
void input()
{
	cin >> N >> A >> B >> K;
	make_contents();
}


//計算
void calc()
{
	ll res = 0;
	REP(numA, N + 1) {
		ll will = K - A * numA;
		if (will%B != 0)continue;
		will /= B;
		if (will > N)continue;

		ll tmp = comb(N, numA)*comb(N, will);
		tmp %= MOD;
		res += tmp;
		res %= MOD;
	}
	cout << res << endl;
}


//出力
void output()
{

}


//デバッグ
void debug()
{
	int N;
	cin>>N;
}


//メイン関数
int main()
{
	input();
	calc();
	output();
	debug();
	
	return 0;
}

Submission Info

Judge Result