結果

問題 No.474 色塗り２
ユーザー vjudge1
提出日時 2025-06-23 13:01:34
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,151 bytes
コンパイル時間 820 ms
コンパイル使用メモリ 131,968 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-23 13:01:37
合計ジャッジ時間 2,111 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

class BinomModPrime {
  int p;
  std::vector<int> fa, ifa;

  // Calculate binom(n, k) mod p for n, k < p.
  int calc(int n, int k) {
    if (n < k) return 0;
    long long res = fa[n];
    res = (res * ifa[k]) % p;
    res = (res * ifa[n - k]) % p;
    return res;
  }

 public:
  BinomModPrime(int p) : p(p), fa(p), ifa(p) {
    // Factorials mod p till p.
    fa[0] = 1;
    for (int i = 1; i < p; ++i) {
      fa[i] = (long long)fa[i - 1] * i % p;
    }
    // Inverse of factorials mod p till p.
    ifa[p - 1] = p - 1;  // Wilson's theorem.
    for (int i = p - 1; i; --i) {
      ifa[i - 1] = (long long)ifa[i] * i % p;
    }
  }

  // Calculate binom(n, k) mod p.
  int binomial(long long n, long long k) {
    long long res = 1;
    while (n || k) {
      res = (res * calc(n % p, k % p)) % p;
      n /= p;
      k /= p;
    }
    return res;
  }
};

int main() {
  int t, p;
  std::cin >> t;
  p=2;
  BinomModPrime bm(p);
  for (; t; --t) {
    long long a,b,c;
    std::cin >> a>>b>>c;
    long long d=c*bm.binomial(b+c-1,b)%2ll;
    std::cout << bm.binomial(d+a-1,a)*c%2ll << '\n';
  }
  return 0;
}
0