結果

問題 No.474 色塗り2
ユーザー 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));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0