Description：

$A$ 物品价值为 $a$ ， $B$ 物品价值为 $b$ ， $C$ 物品价值为 $a+b$ ， $n$ 个位置可以放也可以不放，求价值和为 $k$ 的摆放方案数。

$1\leqslant n\leqslant 10^7$

Solution：

$C$ 物品价值 $a+b$ 考虑怎么处理，发现可以看成先随便放 $A$ ，然后随便放 $B$ ，他们都放的位置看成放 $C$ ，所以如果放了 $a$ 个 $A$ ，那么方案数就是 $C_n^a\times C_n^\frac{K-a\times A}B$ ，所以枚举 $a$ 预处理阶乘和逆元求组合数就行了，注意有数为 $0$ 时有很多特判。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

typedef long long ll;

ll A,B,K;

#define MAXN 10000010

#define MOD 998244353

int fac[MAXN],inv[MAXN];

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int C(int n,int m)

{

	return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

int main()

{

	freopen("biscuits.in","r",stdin);

	freopen("biscuits.out","w",stdout);

	fac[0] = 1;for(register int i = 1;i < MAXN;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	inv[MAXN - 1] = power(fac[MAXN - 1],MOD - 2);

	inv[0] = 1;for(register int i = MAXN - 2;i >= 1;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	scanf("%d%lld%lld%lld",&n,&A,&B,&K);

	if(A == 0 && B == 0)

	{

		if(K == 0)

		{

			int res = 1;

			for(int i = 1;i <= n;++i)res = 1ll * res * 4 % MOD;

			cout << res << endl;

			return 0;

		}

		else

		{

			puts("0");

			return 0;

		}

	}

	if(A == 0)

	{

		if(K == 0)

		{

			int res = 1;

			for(int i = 1;i <= n;++i)res = res * 2 % MOD;

			cout << res << endl;

			return 0;

		}

		else if(K % B != 0 || K / B > n)

		{

			puts("0");

			return 0;

		}

		else

		{

			int res = C(n,K / B);

			for(int i = 1;i <= n;++i)res = res * 2 % MOD;

			cout << res << endl;

			return 0;

		}

	}

	if(B == 0)

	{

		if(K == 0)

		{

			int res = 1;

			for(int i = 1;i <= n;++i)res = res * 2 % MOD;

			cout << res << endl;

			return 0;

		}

		else if(K % A != 0 || K / A > n)

		{

			puts("0");

			return 0;

		}

		else

		{

			int res = C(n,K / A);

			for(int i = 1;i <= n;++i)res = res * 2 % MOD;

			cout << res << endl;

			return 0;

		}

	}

	int ans = 0;

	for(int a = 0;a <= n;++a)

	{

		if((K - a * A) % B == 0)

		{

			ll b = (K - a * A) / B;

			if(b > n)continue;

			if(b < 0)continue;

			ans = (ans + 1ll * C(n,a) * C(n,b)) % MOD;

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}