結果

問題 No.474 色塗り２
コンテスト
ユーザー tanzaku
提出日時 2016-12-21 10:42:37
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,589 ms / 2,000 ms
コード長 2,026 bytes
コンパイル時間 3,770 ms
コンパイル使用メモリ 78,952 KB
実行使用メモリ 109,340 KB
最終ジャッジ日時 2024-12-14 14:22:52
合計ジャッジ時間 6,830 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

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

	void solve() {
//		test();
		precalc();
		
		try (final Scanner in = new Scanner(System.in)) {
			int T = in.nextInt();
			while (T-- > 0) {
				int A = in.nextInt();
				int B = in.nextInt();
				int C = in.nextInt();
//				System.out.println(slow(A, B, C));
				System.out.println(solve(A, B, C));
			}
		}
	}

	final int mod = 2<<20;
	final long[] factFactor2 = new long[mod];
	final long[] factMod1048576 = new long[mod];
	
	void precalc() {
		factMod1048576[0] = 1;
		for (int i = 1; i < mod; i++) {
			int j, factor2 = 0;
			for (j = i; j % 2 == 0; j /= 2) factor2++;
			factMod1048576[i] = factMod1048576[i-1] * j % mod;
			factFactor2[i] = factFactor2[i-1] + factor2;
		}
	}
	
	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 = factMod1048576[n+r-1] * modInverse(factMod1048576[r], mod) % mod * modInverse(factMod1048576[n-1], mod) % 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