Submission #2612868

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll M=998244353LL;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { assert(y%M!=0); return MUL(x, POW(y, M-2)); }
//ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

// ax+by=gcd(a,b) を満たすx,yを1組求めたい時に
ll extgcd(ll a, ll b, ll &x, ll &y, ll c=1, ll d=0, ll e=0, ll f=1) {
  if (b == 0) {
    x = c; y = e;  // dot([c,d; e,f], [1;0])
    return a;
  }
  ll q = a/b, r = a%b;
  return extgcd(b, r, x, y, d, c-q*d, f, e-q*f);  // dot([c,d; e,f], [0,1; 1,-q])
}

pair<ll,ll> abc(ll a, ll b, ll c){
    // ax + by = c
    ll g = gcd(gcd(a,b),c);
    a /= g; b /= g; c /= g;

    ll x, y;
    extgcd(a,b,x,y);
    x *= c, y *= c;
#ifdef DEBUG
    // printf("%lldx + %lldy = %lld -> (x=%lld, y=%lld)\n", a*g,b*g,c*g, x,y);
#endif
    return make_pair(x, y);
}

int N, A, B;
ll K;
ll fact[300001];
vector<ll> combN(300001, 0);

ll pat(ll r, ll g, ll b, ll n){
    if (r<0 || g<0 || b<0) return 0;
    ll n_ = fact[N];
//    ll rgb_ = MUL(MUL(fact[r], fact[g]), fact[b]);
    ll rgb_ = MUL(MUL(fact[r], fact[g]),
                MUL(fact[b], fact[N-r-g-b]));
    return DIV(n_, rgb_);
}
inline ll comb(ll _n, ll x){
    if (x < 0 || N < x) return 0;
    return combN[x];
}

ll solve() {
    // Ax + By = K な x,yを求める

    ll gab = gcd(A,B);
    ll a_ = A / gab, b_ = B / gab;

    pair<ll,ll> xy = abc(A,B,K);
    ll x = xy.first, y = xy.second;
    if (y < 0) {
        ll dy = -y / a_;
        y += a_ * dy;
        x -= b_ * dy;
        if (y < 0) { y += a_; x -= b_; }
    }
    if (x < 0) {
        ll dx = -x / b_;
        x += b_ * dx;
        y -= a_ * dx;
        if (x < 0) { x += b_; y -= a_; }
    }
    if (x < 0 || y < 0) return 0;
    // y>=0, x>= 0

    ll ans = 0;
    for (ll xi=x,yi=y; xi>=0 && yi<=K; ) {
        // printf("(%lld, %lld)\n", xi, yi);
        ans = ADD(ans, MUL(comb(N, xi), comb(N,yi)));
        xi -= b_; yi += a_;
    }
    for (ll xi=x+b_, yi=y-a_; xi<=K && yi>=0; ) {
        // printf("(%lld, %lld)\n", xi, yi);
        ans = ADD(ans, MUL(comb(N, xi), comb(N,yi)));
        xi += b_; yi -= a_;
    }

    return ans;
}

int main() {
    cin >> N >> A >> B >> K;

    fact[0] = fact[1] = 1LL;
    for (ll i=2; i<=300000; ++i) {
        fact[i] = MUL(fact[i-1], i);
    }
    ll c0 = 1;
    combN[0] = 1;
    for (int i=1; i<=300000; ++i) {
        combN[i] = DIV( MUL(combN[i-1], N+1-i), i);
        // cerr << combN[i] << " ";
    }

    cout << solve() << endl;
    return 0;
}

Submission Info

Judge Result