結果

問題 No.474 色塗り2
ユーザー ricky
提出日時 2016-12-24 01:05:53
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 106 ms
コード長 1,617 Byte
コンパイル時間 986 ms
使用メモリ 40,908 KB
最終ジャッジ日時 2019-06-20 06:35:33

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
1.txt AC 23 ms
40,900 KB
2.txt AC 23 ms
40,908 KB
3.txt AC 23 ms
40,908 KB
large1.txt AC 106 ms
40,908 KB
sample.txt AC 24 ms
40,908 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