結果

問題 No.474 色塗り２
コンテスト
ユーザー sigma425
提出日時 2016-12-24 02:10:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 473 ms / 2,000 ms
コード長 1,555 bytes
コンパイル時間 1,313 ms
コンパイル使用メモリ 158,844 KB
実行使用メモリ 34,648 KB
最終ジャッジ日時 2024-12-14 17:09:03
合計ジャッジ時間 3,398 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}

typedef unsigned int UI;
const int MX=2000000;

int osum[MX+1];
UI f[MX+1],g[MX+1],inv[MX+1];
typedef unsigned long long ll;

ll extgcd(ll a,ll b,ll &x,ll &y){
	ll u[]={a,1,0},v[]={b,0,1};
	while(*v){
		ll t=*u/ *v;
		rep(i,3) swap(u[i]-=t*v[i],v[i]);
	}
	x=u[1],y=u[2];
	return u[0];
}
UI iv(UI a){
	ll x,y;
	extgcd(a,1ULL<<32,x,y);
	return x%(1LL<<32);
}

UI C(int a,int b){
	int ord=osum[a]-osum[b]-osum[a-b];
	if(ord>=32) return 0;
	UI ret=f[a]*g[b]*g[a-b];
	rep(i,ord) ret*=2;
	return ret;
}
int solve(){
	UI a,b,c;
	cin>>a>>b>>c;
	if(c%2==0) return 0;
	UI x=c*C(b+c-1,b);
	UI p=a+x-1;
	UI q=a;
	return (p&q)==q;
}
int main(){
	f[0]=1;
	g[0]=1;
	rep1(i,MX){
		int j=0;
		int tmp=i;
		while(tmp%2==0) tmp/=2,j++;
		osum[i]=j;
		f[i]=f[i-1]*tmp;
	}
	rep(i,MX) osum[i+1]+=osum[i];
	rep1(i,MX+1){
		if(i%2==0){
			inv[i]=inv[i/2];
		}else{
			inv[i]=iv(i);
		}
	}
	rep1(i,MX){
		g[i]=g[i-1]*inv[i];
	}
	int T;
	cin>>T;
	rep(i,T) cout<<solve()<<endl;
}
0