結果

問題 No.474 色塗り２
コンテスト
ユーザー pekempey
提出日時 2016-12-24 01:04:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 382 ms / 2,000 ms
コード長 2,382 bytes
コンパイル時間 2,037 ms
コンパイル使用メモリ 185,448 KB
実行使用メモリ 26,916 KB
最終ジャッジ日時 2024-12-14 17:08:08
合計ジャッジ時間 3,486 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct CombinationAnyMod {
	struct CombinationPrimePower {
		int p, q;
		int mod;
		vector<int> F, invF, power, e;

		static pair<int, int> extgcd(int a, int b) {
			if (b == 0) return make_pair(1, 0);
			int x, y;
			tie(x, y) = extgcd(b, a % b);
			return make_pair(y, x - a / b * y);
		}

		static int modulo(int a, int mod) {
			return (a %= mod) < 0 ? a + mod : a;
		}

		static int modinv(int a, int mod) {
			return modulo(extgcd(a, mod).first, mod);
		}

		int mul(int x, int y) {
			return int64_t(x) * y % mod;
		}

		CombinationPrimePower(int n, int p, int q) : p(p), q(q), F(n), invF(n), e(n), power(q + 1) {
			mod = 1;
			for (int i = 0; i < q; i++) mod *= p;

			power[0] = 1;
			for (int i = 1; i <= q; i++) power[i] = mul(power[i - 1], p);

			F[0] = 1;
			for (int i = 1; i < n; i++) {
				F[i] = mul(F[i - 1], i % p == 0 ? 1 : i);
			}

			invF[n - 1] = modinv(F[n - 1], mod);
			for (int i = n - 2; i >= 0; i--) {
				invF[i] = mul(invF[i + 1], (i + 1) % p == 0 ? 1 : i + 1);
			}

			for (int i = 1; i < n; i++) {
				F[i] = mul(F[i], F[i / p]);
				invF[i] = mul(invF[i], invF[i / p]);
				e[i] = i / p + e[i / p];
			}
		}

		int operator()(int n, int r) {
			if (n < 0 || r < 0 || n < r) return 0;
			int f = mul(F[n], mul(invF[n - r], invF[r]));
			return mul(f, power[min(q, e[n] - e[n - r] - e[r])]);
		}
	};

	map<int, int> prime_factors(int n) {
		map<int, int> res;
		for (int i = 2; i * i <= n; i++) {
			for (; n % i == 0; n /= i) res[i]++;
		}
		if (n != 1) res[n] = 1;
		return res;
	}

	vector<CombinationPrimePower> cs;
	vector<int> inv;

	CombinationAnyMod(int n, int mod) {
		for (auto kv : prime_factors(mod)) {
			cs.emplace_back(n, kv.first, kv.second);
		}
		int m = 1;
		for (auto &c : cs) {
			inv.push_back(CombinationPrimePower::modinv(m, c.mod));
			m *= c.mod;
		}
	}

	int operator()(int n, int r) {
		int x = 0;
		int mod = 1;
		for (int i = 0; i < cs.size(); i++) {
			int y = cs[i](n, r);
			x += int64_t(y + cs[i].mod - x) * inv[i] % cs[i].mod * mod;
			mod *= cs[i].mod;
		}
		return x;
	}
};

int main() {
	const int mod = 1 << 24;
	CombinationAnyMod c(2020202, mod);

	int T;
	cin >> T;
	while (T--) {
		int A, B, C;
		cin >> A >> B >> C;

		if (C % 2 == 0) {
			puts("0");
			continue;
		}

		int X = (1LL * C * c(C - 1 + B, B) - 1) % mod;
		puts((X & A) != 0 ? "0" : "1");
	}
}
0