結果

問題 No.474 色塗り２
コンテスト
ユーザー tanzaku
提出日時 2016-12-22 22:41:59
言語 Java
(openjdk 23)
結果
AC  
実行時間 800 ms / 2,000 ms
コード長 2,337 bytes
コンパイル時間 6,637 ms
コンパイル使用メモリ 77,868 KB
実行使用メモリ 133,240 KB
最終ジャッジ日時 2024-12-14 14:58:05
合計ジャッジ時間 5,879 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class _474 {
	public static void main(String[] args) throws IOException {
		new _474().solve();
	}

	void solve() throws IOException {
		precalc();
		
		try (final BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
			int T = Integer.parseInt(in.readLine());
			while (T-- > 0) {
				String[] sp = in.readLine().split(" ");
				int A = Integer.parseInt(sp[0]);
				int B = Integer.parseInt(sp[1]);
				int C = Integer.parseInt(sp[2]);
				System.out.println(solve(A, B, C));
			}
		}
	}

	final int mod = 2<<20;
	final long[] factFactor2 = new long[mod];
	final long[] factMod = new long[mod];
	final long[] factInvMod = new long[mod];
	
	void precalc() {
		factMod[0] = 1;
		for (int i = 1; i < mod; i++) {
			int j, factor2 = 0;
			for (j = i; j % 2 == 0; j /= 2) factor2++;
			factMod[i] = factMod[i-1] * j % mod;
			factFactor2[i] = factFactor2[i-1] + factor2;
		}
		factInvMod[mod - 1] = modInverse(factMod[mod - 1], mod);
		for (int i = mod - 1; i > 0; i--) {
			int j;
			for (j = i; j % 2 == 0; j /= 2) ;
			factInvMod[i-1] = factInvMod[i] * j % mod;
		}
	}
	
	int solve(int A, int B, int C) {
		if (C % 2 == 0) {
			return 0;
		}
		
		long[] cHb = H(C, B);
		long bit = ((C * cHb[1] % mod) << Math.min(32, cHb[0])) % mod + A - 1;
		
		// https://hermes-ir.lib.hit-u.ac.jp/rs/bitstream/10086/9464/1/HNshizen0001400750.pdf
		// 定理8より
		return (bit & A) == A ? 1 : 0;
	}
	
	long[] H(int n, int r) {
		long factor2 = factFactor2[n+r-1] - factFactor2[r] - factFactor2[n-1];
		long val = factMod[n+r-1] * factInvMod[r] % mod * factInvMod[n-1] % mod;
		return new long[]{ factor2, val, };
	}
	
	static long modInverse(final long n, final long m) {
		final long[] res = extGcd(n, m);
		if (res[2] != 1) {
			dump(n, m, res);
			throw new RuntimeException();
		}
		return (m + res[0]) % m;
	}

	static long[] extGcd(final long a, final long b) {
		if (b == 0) {
			return new long[] { 1, 0, a };
		}
		final long[] res = extGcd(b, a % b);
		long y = res[0];
		final long x = res[1];
		y -= (a / b) * x;
		res[0] = x;
		res[1] = y;
		return res;
	}

	// for debug
	static void dump(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}
0