階乗逆元+巧みな解法

B - RGB Coloring
Time limit時間制限:2 sec/Memory limit Memory制限:1024 MB
配点:700点
問題文
高桥君拥有1个塔瓦,那是N个布洛克成长一列.第一次全部的黑色是无色,但高桥君用红色、绿色、蓝色的各种色涂上几个黑色,所以想让塔瓦变得美丽.因此,高桥先生将塔瓦的美丽定义为以下.

各黑色的得点,如果赤色涂上的话,A点,绿色涂上的话,A+B点,蓝色涂上的话,B点,无色的话0点,以N个黑色的得点的合计为塔瓦的美丽.

但是,A,B是被赋予的正整数的定数,各口罩2个以上的颜色同时都没有涂上.
我认为高桥君正好像成为K,涂布布布洛克.那样的涂上黄油的方法有什么呐.请允许我在998244353中要求剩下的剩余.但是,涂上两种纹纹的方法不同的话,有些黑色存在,涂在那个黑色中的颜色不同,另一方面被涂,但另一方面是无色的.
制約

1≦N≦3×105

1≦A,B≦3×105

0≦K≦18×1010

输入的价格全部是整数的

にゅうりょく
入力由以下形式提供标准入力.

N A B K

力を出す
998244353把涂上塔瓦的方法的个数割成了剩余的力量.
入力例1
Copy

4 1 2 5

出力例1
Copy

40

在这种情况下,1个红色,1个绿色,3个蓝色,2个蓝色,所以5个美度,

緑1個、青1個

赤1個、青2個

赤2個、緑1個

赤3個、青1個

仅仅是在某个情况下.因此,要求的回答变成40.
入力例2
Copy

2 5 6 0

出力例2
Copy

1

美丽0的塔瓦只是所有的黑色.因此,回答是1.
入力例3
Copy

90081 33447 90629 6391049189

出力例3
Copy

577742975

Score : 700 points
Problem Statement
Takahashi has a tower which is divided into N layers. Initially, all the layers are uncolored. Takahashi is going to paint some of the layers in red, green or blue to make a beautiful tower. He defines the beauty of the tower as follows:

The beauty of the tower is the sum of the scores of the N layers, where the score of a layer is A if the layer is painted red, A+B if the layer is painted green, B if the layer is painted blue, and 0 if the layer is uncolored.

Here, A and B are positive integer constants given beforehand. Also note that a layer may not be painted in two or more colors.
Takahashi is planning to paint the tower so that the beauty of the tower becomes exactly K. How many such ways are there to paint the tower? Find the count modulo 998244353. Two ways to paint the tower are considered different when there exists a layer that is painted in different colors, or a layer that is painted in some color in one of the ways and not in the other.
Constraints

1≤N≤3×105

1≤A,B≤3×105

0≤K≤18×1010

All values in the input are integers.

Input
Input is given from Standard Input in the following format:

N A B K

Output
Print the number of the ways to paint tiles, modulo 998244353.
Sample Input 1
Copy

4 1 2 5

Sample Output 1
Copy

40

In this case, a red layer worth 1 points, a green layer worth 3 points and the blue layer worth 2 points. The beauty of the tower is 5 when we have one of the following sets of painted layers:

1 green, 1 blue

1 red, 2 blues

2 reds, 1 green

3 reds, 1 blue

The total number of the ways to produce them is 40.
Sample Input 2
Copy

2 5 6 0

Sample Output 2
Copy

1

The beauty of the tower is 0 only when all the layers are uncolored. Thus, the answer is 1.
Sample Input 3
Copy

90081 33447 90629 6391049189

Sample Output 3
Copy

577742975

代码

#include
using namespace std;
#define N 300007
#define MAX 300000
#define mod 998244353
long long fac[N];
long long inv[N];
long long quick_power(long long p,long long t)//    
{
	long long sum=1;
	while(t)
	{
		if(t&1) sum=sum*p%mod;
		p=p*p%mod;
		t>>=1;
	}
	return sum;
}

void pre()//    ，       
{
	fac[0]=1;
	for(long long i=1;i<=MAX;++i)
		fac[i]=(i*fac[i-1])%mod;
	inv[MAX]=quick_power(fac[MAX],mod-2);
	for(long long i=MAX-1;i>=0;--i)
		inv[i]=inv[i+1]*(i+1)%mod;
}

long long Cc(long long a,long long b)
{
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}

int main()
{
	pre();
	long long n,a,b,k;
	cin>>n>>a>>b>>k;
	long long sum=0; 
	for(long long i=0;i<=n&&i*a<=k;++i)
	{
		long long left=k-i*a;
		if(left%b==0&&(left/b)<=n)
		{
			long long j=left/b;
			sum=sum+Cc(n,i)*Cc(n,j)%mod; 
		}
	}
	cout<