Submission #8474225


Source Code Expand

Copy
#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

Submission Time
Task D - Knight
User tkmtSo
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1590 Byte
Status AC
Exec Time 4 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01, sample_02, sample_03
All hand_01, hand_02, hand_03, hand_04, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, random_14, random_15, random_16, random_17, random_18, random_19, random_20, random_21, random_22, random_23, random_24, sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
hand_01 AC 1 ms 256 KB
hand_02 AC 1 ms 256 KB
hand_03 AC 1 ms 256 KB
hand_04 AC 1 ms 256 KB
random_01 AC 1 ms 256 KB
random_02 AC 1 ms 256 KB
random_03 AC 1 ms 256 KB
random_04 AC 1 ms 256 KB
random_05 AC 1 ms 256 KB
random_06 AC 2 ms 256 KB
random_07 AC 1 ms 256 KB
random_08 AC 1 ms 256 KB
random_09 AC 1 ms 256 KB
random_10 AC 3 ms 256 KB
random_11 AC 1 ms 256 KB
random_12 AC 4 ms 256 KB
random_13 AC 2 ms 256 KB
random_14 AC 2 ms 256 KB
random_15 AC 3 ms 256 KB
random_16 AC 1 ms 256 KB
random_17 AC 4 ms 256 KB
random_18 AC 4 ms 256 KB
random_19 AC 4 ms 256 KB
random_20 AC 4 ms 256 KB
random_21 AC 4 ms 256 KB
random_22 AC 4 ms 256 KB
random_23 AC 4 ms 256 KB
random_24 AC 4 ms 256 KB
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 4 ms 256 KB