Language: C++

#include<iostream>
#include<vector>
#include<stdint>
using namespace std;

const int MOD = 998244353; // 今回使う余り
typedef class factorial{
	private:
		int mod;
		int n;
		vector<int> fact, inv;
		void calc();
	public:
		factorial(int mod, int n);
		int add(int a, int b);
		int sub(int a, int b);
		int mul(int a, int b);
		int div(int a, int b);
		int rem(int a, int b);
		int power(int a, int b);
		int getCombination(int a, int b);
		int getPermutation(int a, int b);
		int getFactorial(int a);
		int getInverse(int a);
} Factorial;

/**
 * 関数の初期化を行います。この時に空間O(n)と計算時間O(n)が必要なことに注意してください。
 * @param mod 用いる余り ※必ず素数にすること
 * @param n 用意する階乗の範囲
 */
factorial::factorial(int mod, int n) {
	factorial::mod = mod;
	factorial::n = n;
	fact.resize(n + 1, 1);
	inv.resize(n + 1, 1);
	calc();
}

void factorial::calc() {
	for (int i = 1;i <= n;++i) {
		fact[i] = mul(fact[i - 1], i);
	}
	inv[n] = power(fact[n], mod - 2);
	for (int i = n - 1;i >= 0;--i) {
		inv[i] = mul(inv[i + 1], i + 1);
	}
}

/**
 * a+bをmod環境下で返します。
 * @param a 足す値
 * @param b 足される値
 * @return (a + b) % mod
 */
int factorial::add(int a, int b) {
	return ((int64_t)a + b) % mod;
}

/**
 * a-bをmod環境下で返します。
 * @param a 引く値
 * @param b 引かれる値
 * @return (a - b) % mod
 */
int factorial::sub(int a, int b) {
	return ((int64_t)a - b) % mod;
}

/**
 * a*bをmod環境下で返します。
 * @param a 掛ける値
 * @param b 掛けられる値
 * @return (a * b) % mod
 */
int factorial::mul(int a, int b) {
	return ((int64_t)a * b) % mod;
}

/**
 * a/bをmod環境下で返します。O(log(mod))な点にご注意ください
 * @param a 割る値
 * @param b 割られる値
 * @return (a / b) % mod
 */
int factorial::div(int a, int b) {
	return mul(a, power(b, mod - 2));
}

/**
 * a%bを返します。
 * @param a 割る値
 * @param b 割られる値
 * @return a % b
 */
int factorial::rem(int a, int b) {
	return a % b;
}

/**
 * aのb乗をmod環境下で返します。
 * @param a 底
 * @param b 冪指数
 * @return pow(a, b) % mod
 */
int factorial::power(int a, int b) {
	if (b == 0) return 1;
	if (b == 1) return a;
	if (b == 2) return mul(a, a);
	if ((b & 1) == 0) return power(power(a, b >> 1), 2);
	return mul(power(power(a, b >> 1), 2), a);
}

/**
 * aCbをmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aCb) % mod
 */
int factorial::getCombination(int a, int b) {
	return mul(getPermutation(a, b), getInverse(b));
}

/**
 * aPbをmod環境下で返します。
 * @param a 元集合
 * @param b 元
 * @return (aPb) % mod
 */
int factorial::getPermutation(int a, int b) {
	return mul(getFactorial(a), getInverse(a - b));
}

/**
 * a!をmod環境下で返します。
 * @param a 計算する値
 * @return a! % mod
 */
int factorial::getFactorial(int a) {
	return fact[a];
}

/**
 * a!の-1乗をmod環境下で返します。
 * @param a 計算する値
 * @return pow(a!, -1) % mod
 */
int factorial::getInverse(int a) {
	return inv[a];
}

int main() {
	int N, A, B;
	int64_t K;
	cin >> N >> A >> B >> K;
	
	Factorial fact(MOD, N);
	int ans = 0;
	
	for (int r = 0, b;r <= N;r ++) { // 赤と緑の合計個数
		if ((K - A * r) % B != 0) continue; // 割り切れないならそんな個数は作れない
		b = (K - A * r) / B;
		if (b > N) continue; // 青+緑の個数がブロック数より多いとか無いから
		// この時、(r, b)についてrが赤+緑の個数、bが緑+青の個数
		/*
		ここで、次のように考える
		1. Nマス中のrマスを赤色に塗る
		2. Nマス中のbマスを青色に塗る
		3. 赤色に塗っていた場所に青色を塗ると、混ざって何故か緑色になる
		こうすると計算が簡単にできるね、例えばNマス中rマスを選ぶ選び方はNCrだし
		*/
		ans = fact.add(ans, fact.mul(fact.getCombination(N, r), fact.getCombination(N, b)));
	}
	cout << ans;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり

まず、Ax+By=Kかつx,y≦Nとなるようなx, yについて求める O(N)
細かいことはコメントに直で解説書いてるので上見て

ちなみにmodが素数なら逆元ライブラリ持っておくとコンビネーションがあっという間に計算できるよ
*/

Compiler output:
a.cc:3:9: fatal error: stdint: No such file or directory
    3 | #include<stdint>
      |         ^~~~~~~~
compilation terminated.