Submission #8474225

---

Source Code Expand

#include <iostream>
#include <vector>
#include <tuple>

using lli=long long int;
const lli mod=1000000007;

constexpr lli mod_normalize(lli a){
  return ((a%mod)+mod)%mod;
}

constexpr lli mod_inv(lli a){
  lli b=mod, u=1, v=0, tmp=0;
  while(b){
    lli t = a/b;
    a -= t*b;
    tmp = a; a = b; b = tmp; //swap(a, b);
    u -= t*v;
    tmp = u; u = v; v = tmp; //swap(u, v);
  }
  return mod_normalize(u);
}

constexpr lli fac_pre_num = 100100;
struct fac_pre_struct{
  lli fac[fac_pre_num], finv[fac_pre_num];
  constexpr fac_pre_struct() : fac{}, finv{} {
    fac[0] = fac[1] = finv[0] = finv[1] = 1;
    for(int i = 2; i < fac_pre_num; i++) fac[i] = i*fac[i-1] % mod;
    finv[fac_pre_num-1] = mod_inv(fac[fac_pre_num-1]);
    for(int i = fac_pre_num-1; i > 2; i--) finv[i-1] = i*finv[i] % mod;
  }
};
constexpr fac_pre_struct fac_pre;

std::tuple<lli, lli, lli> fac_3_mod(lli a, lli b, lli c){
  lli t = 1;
  lli tb=1, tc=1;
  for(int i = 1; i <= a; i++){
    t = (t*i)%mod;
    if(i == b) tb = t;
    if(i == c) tc = t;
  }
  return std::make_tuple(t, tb, tc);
}

lli mod_comb(lli n, lli k){
  if(n < k || k < 0 || n < 0) return 0;
  if(n < fac_pre_num) return fac_pre.fac[n] * (fac_pre.finv[k] * fac_pre.finv[n-k] % mod) % mod;
  lli fn, fk1, fk2;
  std::tie(fn, fk1, fk2) = fac_3_mod(n, k, n-k);
  return fn * (mod_inv(fk1) * mod_inv(fk2) % mod) % mod;
}

int main(){
  lli X,Y;
  std::cin >> X >> Y;

  if((X+Y)%3 != 0){
    std::cout << 0 << std::endl;
    return 0;
  }
  lli dx = X-(X+Y)/3;

  lli ans = mod_comb((X+Y)/3, dx);
  std::cout << ans << std::endl;

  return 0;
}

Submission Info

Judge Result