結果

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

ソースコード

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();
		
		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(solve(A, B, C));
			}
		}
	}
	
	void test() {
		for (int A = 1; A <= 100; A++) {
			for (int B = 1; B <= 100; B++) {
				for (int C = 1; C <= 100; C++) {
					if (slow(A, B, C) != solve(A, B, C)) {
						dump(A, B, C);
						dump(slow(A, B, C), solve(A, B, C));
						throw new RuntimeException();
					}
				}
			}
		}
		throw new RuntimeException();
	}
	
	int slow(int A, int B, int C) {
		BigInteger b = BigInteger.valueOf(C).pow(B + 1);
		BigInteger v = BigInteger.ONE;
		for (int i = 0; i < A; i++) {
			v = v.multiply(b.add(BigInteger.valueOf(i)));
			v = v.divide(BigInteger.valueOf(i + 1));
		}
		return v.multiply(BigInteger.valueOf(C)).mod(BigInteger.valueOf(2)).intValue();
	}
	
	// H(C^(B+1),A) * C mod 2
	int solve(int A, int B, int C) {
		if (C % 2 == 0) {
			return 0;
		}
		
		long d = pow(C, B + 1);
		return count2(d, d + A - 1) == count2(1, A) ? 1 : 0;
	}
	
	// [l, r]
	long count2(long l, long r) {
		return count2(r) - count2(l-1);
	}
	
	long count2(long n) {
		long ans = 0;
		for (long pow2 = 2; pow2 <= n; pow2 *= 2) {
			ans += n / pow2;
		}
		return ans;
	}
	
	long pow(int n, int r) {
		final int mod = 1<<29;
		if (r == 0) return 1;
		long x = pow(n, r / 2);
		x = x * x % mod;
		if (r % 2 == 1) x = x * n % mod;
		return x;
	}

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