結果

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

テストケース

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