結果

問題 No.474 色塗り２
ユーザー kyuridenamida
提出日時 2016-12-24 02:42:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 357 ms / 2,000 ms
コード長 1,103 bytes
コンパイル時間 2,054 ms
コンパイル使用メモリ 165,460 KB
実行使用メモリ 69,088 KB
最終ジャッジ日時 2024-12-14 17:10:17
合計ジャッジ時間 2,706 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:66:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   66 | main(){
      | ^~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int __int128
map<int,vector<int> > factored;

const int MOD = 1ll<<41;
int PHI = MOD / 2;
int frac[1111111];


int bpow(int a,int b){
	return b?bpow(a*a%MOD,b/2)*(b&1?a:1)%MOD:1;
}

struct Number{
	int twos;
	int val;
	Number(){ val = 1; twos = 0; }
	Number(int n){
		twos = val = 0;
		while( n % 2 == 0 ) n /= 2, twos++;
		val = n;
		val %= MOD;
	}
	int v(){
		if( twos >= 21 ) return 0;
		return val * (1<<twos) % MOD;
	}
};
Number operator * (Number a,Number b){
	a.twos += b.twos;
	a.val *= b.val;
	a.val %= MOD;
	return a;
}

Number operator / (Number a,Number b){
	a.twos -= b.twos;
	
	a.val *= bpow(b.val,PHI-1);
	a.val %= MOD;
	return a; 
}


int T(int n,int k){
	return !(~n & k);
}


Number fr[1<<21];

Number nCr(int n,int r){
	return fr[n]/fr[n-r]/fr[r];
}

int solver(int A,int B,int C){
	return T(nCr(B+C-1,C-1).v()*C+A-1,A)%2*C%2;
}






main(){
	for(int i = 1 ; i < (1<<21) ; i++){
		fr[i] = fr[i-1] * i;
	}
	
	signed T;
	cin >> T;
	
	while(T--){
		signed A,B,C;
		cin >> A >> B >> C;
		cout << (signed)solver(A,B,C) << endl;
	}
	
}
0