結果

問題 No.474 色塗り２
ユーザー kyuridenamidakyuridenamida
提出日時 2016-12-24 02:42:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 363 ms / 2,000 ms
コード長 1,103 bytes
コンパイル時間 1,889 ms
コンパイル使用メモリ 164,956 KB
実行使用メモリ 68,992 KB
最終ジャッジ日時 2024-05-08 13:01:31
合計ジャッジ時間 3,145 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 62 ms
68,864 KB
testcase_01 AC 62 ms
68,864 KB
testcase_02 AC 60 ms
68,992 KB
testcase_03 AC 363 ms
68,992 KB
testcase_04 AC 62 ms
68,992 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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