結果

問題 No.474 色塗り２
ユーザー vjudge1
提出日時 2025-06-20 17:50:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 301 ms / 2,000 ms
コード長 2,577 bytes
コンパイル時間 2,327 ms
コンパイル使用メモリ 197,972 KB
実行使用メモリ 50,788 KB
最終ジャッジ日時 2025-06-20 17:50:06
合計ジャッジ時間 3,225 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
bool st;
using namespace std;
template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;}
template<typename T>ostream&operator<<(ostream&O,vector<T> v){for(auto i:v)O<<i<<' ';return O;}
string TMP,STR;
stringstream CIN;
void read_all(){
#ifdef debug
	cerr<<"----------------------------------- START -----------------------------------\n";
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(getline(cin,TMP))STR+=TMP,STR+='\n';
	CIN.str(STR);
	cerr<<"\n--------------------------------- INPUT END ---------------------------------\n";
#endif
}
#ifdef debug
#define cin CIN
#endif
namespace AC{
int calc(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 calc(n/2,k/2);
}
void exgcd(int a,int b,int&x,int&y){
	x=1;
	y=0;
	if(b!=0){
		exgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}
}
int inv(int v,int m){
	int x,y;
	exgcd(v,m,x,y);
	return (x+m)%m;
}
const int N=3e6;
const int mod=1<<24;
int fac[N];
int bow[N];
bool bl=0;
void solve(){
	if(!bl){
		bl=1;
		fac[0]=1;
		bow[0]=0;
		for(int i=1;i<N;i++){
			int v=i;
			bow[i]=bow[i-1];
			while(v%2==0){
				bow[i]++;
				v/=2;
			}
			fac[i]=fac[i-1]*v%mod;
		}
	}
	int a,b,c;
	cin>>a>>b>>c;
	if(c%2==0){
		cout<<0<<endl;
		return;
	}
	int x=fac[c+b-1]*inv(fac[b],mod)%mod*inv(fac[c-1],mod)%mod*c%mod;
	int bin=bow[c+b-1]-bow[b]-bow[c-1];
	while(x!=0&&bin>0){
		x=x*2%mod;
		bin--;
	}
	x=(x+a-1+mod)%mod;
	int cnt=31-__builtin_clz(a)+1;
	cnt=(1<<cnt)-1;
	int chk=(~x)&(a)&cnt;
	int ans=chk!=0?0:1;
	cout<<ans<<endl;
}
}
bool ed;
signed main(){
	chrono::steady_clock::time_point St=chrono::steady_clock::now();
	read_all();
	chrono::steady_clock::time_point ST=chrono::steady_clock::now();
	int t=1;
	cin>>t;
	while(t--)AC::solve();
	chrono::steady_clock::time_point ED=chrono::steady_clock::now();
	cerr<<setprecision(3)<<fixed<<"\n\n------------------------------------ END ------------------------------------\n"<<"Total Time   : "<<left<<setw(10)<<chrono::duration_cast<chrono::milliseconds>(ED-St).count()<<" \tms\n"<<"Real  Time   : "<<left<<setw(10)<<chrono::duration_cast<chrono::milliseconds>(ED-ST).count()<<" \tms\n"<<"             : "<<left<<setw(10)<<chrono::duration_cast<chrono::microseconds>(ED-ST).count()<<" \t?s\n\n"<<"Total Memory : "<<left<<setw(10)<<(&ed-&st)/1048576.0<<" \tMB\n"<<"               "<<left<<setw(10)<<(&ed-&st)/1024.0<<" \tKB\n"<<"               "<<left<<setw(10)<<(&ed-&st)<<" \tByte\n";
}
0