結果

問題 No.474 色塗り２
ユーザー rickythetarickytheta
提出日時 2016-12-24 01:05:53
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 102 ms / 2,000 ms
コード長 1,617 bytes
コンパイル時間 1,123 ms
コンパイル使用メモリ 145,116 KB
実行使用メモリ 43,172 KB
最終ジャッジ日時 2023-08-21 07:44:52
合計ジャッジ時間 1,855 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
42,960 KB
testcase_01 AC 18 ms
42,968 KB
testcase_02 AC 19 ms
43,028 KB
testcase_03 AC 102 ms
43,172 KB
testcase_04 AC 19 ms
42,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl

// parity of combination
int parity(int n,int k){
  if(k<0 || k>n)return 0;
  if(k==0 || k==n)return 1;
  if(n%2==0 && k%2==1)return 0;
  return parity(n/2, k/2);
}

void extgcd(ll a,ll b,ll &x,ll &y){
  x=1;
  y=0;
  if(b!=0){
    extgcd(b,a%b,y,x);
    y -= (a/b) * x;
  }
}
ll modinv(ll v,ll m){
  ll x,y;
  extgcd(v,m,x,y);
  return (x+m)%m;
}
const int YO = 2521830;
ll fact[YO];
ll bow[YO];

int main(){
  const int MO = 1<<24;
  fact[0] = 1;
  bow[0] = 0;
  FOR(i,1,YO){
    int v = i;
    bow[i] = bow[i-1];
    while(v%2==0){
      bow[i]++;
      v/=2;
    }
    fact[i] = fact[i-1]*v % MO;
  }
  int t;
  scanf("%d",&t);
  while(t--){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(c%2==0){
      puts("0");
      continue;
    }
// C * comb(C*comb(C+B-1,B)+A-1,A) mod 2
// parity check with C*comb(C+B-1,B)+A-1, A
// so we need (C*comb(C+B-1,B)+A-1) mod 2^20
    ll x = fact[c+b-1] * modinv(fact[b],MO) % MO * modinv(fact[c-1],MO) % MO * c % MO;
    ll bin = bow[c+b-1] - bow[b] - bow[c-1];
    while(x!=0 && bin>0){
      x = x*2%MO;
      bin--;
    }
    x = (x+a-1+MO)%MO;
    int bitflag = 31-__builtin_clz(a)+1;
    bitflag = (1<<bitflag) - 1;
    int check = (~x)&(a)&bitflag;
    int par = check!=0 ? 0 : 1;
    printf("%d\n",par);
  }
  return 0;
}
0