結果

問題 No.474 色塗り２
ユーザー tanzakutanzaku
提出日時 2016-12-21 02:51:23
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 1,775 bytes
コンパイル時間 3,360 ms
コンパイル使用メモリ 79,920 KB
実行使用メモリ 70,764 KB
最終ジャッジ日時 2024-05-08 11:01:14
合計ジャッジ時間 5,897 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 122 ms
54,144 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 125 ms
53,820 KB
権限があれば一括ダウンロードができます

ソースコード

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