結果

問題 No.474 色塗り2
ユーザー kyuridenamidakyuridenamida
提出日時 2016-12-24 02:42:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 356 ms / 2,000 ms
コード長 1,103 bytes
コンパイル時間 1,452 ms
コンパイル使用メモリ 148,976 KB
実行使用メモリ 71,176 KB
最終ジャッジ日時 2023-08-21 07:46:15
合計ジャッジ時間 2,557 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
71,176 KB
testcase_01 AC 37 ms
70,996 KB
testcase_02 AC 40 ms
71,096 KB
testcase_03 AC 356 ms
70,936 KB
testcase_04 AC 37 ms
70,888 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:66:6: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
 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