結果

問題 No.474 色塗り２
ユーザー vjudge1
提出日時 2025-06-28 11:49:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,124 bytes
コンパイル時間 1,654 ms
コンパイル使用メモリ 163,152 KB
実行使用メモリ 34,868 KB
最終ジャッジ日時 2025-06-28 11:49:27
合計ジャッジ時間 3,161 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=2e6+5;
int fac[N],inv[N];
int mod=(1<<20);
int ksm(int x,int y){
	if(y==0)return 1;
	int k=ksm(x,y/2);
	if(y&1ll)return k*k%mod*x%mod;
	return k*k%mod;
}
void sl(){
	int a,b,c;
	cin>>a>>b>>c;
	if(c%2==0){
		cout<<"0\n";
		return ;
	}
	int tot=0;
	int u=c;
	while(u%2==0){
		tot++;
		u/=2;
	}
	tot+=fac[b+c-1];
	tot-=fac[c-1]+fac[b];
	int y=u*inv[b+c-1]%mod*ksm(inv[c-1],mod/2-1)%mod*ksm(inv[b],mod/2-1)%mod;
//	cout<<y<<"\n";
	if(tot){
		cout<<"0\n";
	}else {
		int nw=1;
		while(a){
			a/=2;
			nw++;
		} 
		y%=(1<<nw);
		y=(y+(1<<nw)-1)%(1<<nw);
		if((y&a)==0)cout<<"1\n";
		else cout<<"0\n";
	}
}
signed main(){
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout); 
	inv[0]=1;
	for(int i=1;i<=2e6;i++){
		int t=i,cnt=0;
		while(t%2==0){
			cnt++;
			t/=2;
		}
		fac[i]=fac[i-1]+cnt;
		inv[i]=inv[i-1]*t%mod;
	}
	int t;
	cin>>t;
	while(t--)sl();
	return 0;
}
0