AGC025 - B: RGB Coloring

問題

B - RGB Coloring

解説

各マスが 2 つ以上の色で同時に塗られることがないことにも注意してください。

これがミスリードになっている気がする。わざわざ言及しなくても理解できそうな前提なのに。 同時に塗っても良いとすれば、個から赤を個、青を個選ぶ場合の組合せの積となる。

ちょうどの得点に一致すれば良いので、を決め打ちすれば、は割り算で求まる。任意のについて組合せの積の和を取れば良い。

combinationは階乗で計算できるので、階乗をメモっておいてで計算しておく。

コード

int64_t const MOD = 998244353;
 
namespace math { namespace integer {
 
template<class T> T mod_mul(T x, T k, T m) { if(k == 0) { return 0; } if(k % 2 == 0) { return mod_mul((x + x) % m, k / 2, m); } else { return (x + mod_mul(x, k - 1, m)) % m; } }
template<class T> T mod_pow(T x, T n, T mod) { if(n == 0) { return 1; } if(n % 2 == 0) { return mod_pow(mod_mul(x, x, mod) % mod, n / 2, mod); } else { return mod_mul(x, mod_pow(x, n - 1, mod), mod); } }
 
}}
using namespace math::integer;
 
namespace math {
 
constexpr int64_t MaxFact = 300010;
 
template<class T = int64_t>
struct FactRevFactList {
 
  array<T, MaxFact+1> fact_;
  array<T, MaxFact+1> rev_fact_;
 
  FactRevFactList() {
    fact_[0] = 1;
    for(int i=1; i<MaxFact; i++) {
      fact_[i] = fact_[i-1] * i;
      fact_[i] %= MOD;
    }
 
    rev_fact_[MaxFact-1] = mod_pow(fact_[MaxFact-1], (T)MOD-2, MOD);
 
    for(int i=MaxFact-2; i>=0; i--) {
      rev_fact_[i] = rev_fact_[i+1] * (i+1);
      rev_fact_[i] %= MOD;
    }
  }
 
  T fact(int x) const { return fact_[x]; }
  T fact_inv(int x) const { return rev_fact_[x]; }
 
};
 
template<class T = int64_t>
struct CombinationBig {
  math::FactRevFactList<> fr_;
  T comb(T n, T r) { return (fr_.fact(n) * fr_.fact_inv(r) % MOD) * fr_.fact_inv(n-r) % MOD; }
};
 
}
 
math::CombinationBig<> cbig;
 
int main() {
  int64_t N, A, B, K;
  cin >> N >> A >> B >> K;
  int64_t ans = 0;
  rep(a, N + 1) {
    auto rest = K - A * a;
    if (rest < 0) continue;
    auto b = rest / B;
    if (rest % B == 0 && b <= N) {
      ans += cbig.comb(N, a) * cbig.comb(N, b) % MOD;
      ans %= MOD;
    }
  }
  cout << ans << endl;
}