結果

問題 No.474 色塗り2
ユーザー tanzaku
提出日時 2016-12-22 22:41:59
言語 Java
(openjdk 23)
結果
AC  
実行時間 800 ms / 2,000 ms
コード長 2,337 bytes
コンパイル時間 6,637 ms
コンパイル使用メモリ 77,868 KB
実行使用メモリ 133,240 KB
最終ジャッジ日時 2024-12-14 14:58:05
合計ジャッジ時間 5,879 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class _474 {
public static void main(String[] args) throws IOException {
new _474().solve();
}
void solve() throws IOException {
precalc();
try (final BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
int T = Integer.parseInt(in.readLine());
while (T-- > 0) {
String[] sp = in.readLine().split(" ");
int A = Integer.parseInt(sp[0]);
int B = Integer.parseInt(sp[1]);
int C = Integer.parseInt(sp[2]);
System.out.println(solve(A, B, C));
}
}
}
final int mod = 2<<20;
final long[] factFactor2 = new long[mod];
final long[] factMod = new long[mod];
final long[] factInvMod = new long[mod];
void precalc() {
factMod[0] = 1;
for (int i = 1; i < mod; i++) {
int j, factor2 = 0;
for (j = i; j % 2 == 0; j /= 2) factor2++;
factMod[i] = factMod[i-1] * j % mod;
factFactor2[i] = factFactor2[i-1] + factor2;
}
factInvMod[mod - 1] = modInverse(factMod[mod - 1], mod);
for (int i = mod - 1; i > 0; i--) {
int j;
for (j = i; j % 2 == 0; j /= 2) ;
factInvMod[i-1] = factInvMod[i] * j % mod;
}
}
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 = factMod[n+r-1] * factInvMod[r] % mod * factInvMod[n-1] % 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));
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0