Submission #2609272

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef  long long ll;
typedef unsigned long long ull;
const int inf_int=1e8;
const ll inf_ll=1e16;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double dbl;
#define pb push_back
const double pi=3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;

const int MAXN = 3e5+10;
const int LOG = 20;
const int mod =998244353;


ll bin_pow(ll a,int n){
    ll res = 1;
    while(n){
        if(n&1){
            res = (res * a)%mod;
        }
        a = (a*a)%mod;
        n>>=1;
    }
    return res;
}
ll rev(ll x){
    return bin_pow(x,mod-2);
}

ll fac[MAXN];
ll rev_fac[MAXN];

ll A,B;
void precalc(){
    fac[0] = 1;
    rev_fac[0] = 1;
    for(int i=1;i<MAXN;++i){
        fac[i]  =(fac[i-1] * i)%mod;
        rev_fac[i] = rev(fac[i]);
    }

}

ll C(int n,int k){
    return ( (fac[n] * rev_fac[k])%mod * rev_fac[n-k] )%mod;
}

void solve(){
    int n;
    cin >> n;

    cin >> A >> B;
    ll k;
    cin >> k;
    if(k==0){
        cout <<1;
        return;
    }
    precalc();

    ll ans = 0;

    for(int m=0;m<=n;++m){
        //m total green and red
        dout << m<< " : "<<endl;
        if(m * A > k)
            continue;
        ll x = (k - m * A);
        if(x%B!=0)
            continue;
        dout <<"x "<< x<<endl;
        x = x / B;
        if(x<0 || x>n){
            continue;
        }

        ll cur = (C(n,m)  * C(n,x))%mod;
        ans+=cur;
        if(ans>=mod)
            ans-=mod;
    }
    cout << ans<<"\n";

}

signed main()
{
        #ifdef taow
           freopen("input.txt","r",stdin);
         //   freopen("output.txt","w",stdout);
        #else
        #endif // taow
        ios_base::sync_with_stdio(0);
        cin.tie(0); cout.tie(0);
        cout.setf(ios::fixed);
        cout.precision(20);



        int t = 1;
        while(t--)
            solve();
}

Submission Info

Judge Result