結果
問題 | No.474 色塗り2 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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 2int 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));}}