結果

問題 No.474 色塗り2
ユーザー tanzakutanzaku
提出日時 2016-12-21 10:42:37
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,589 ms / 2,000 ms
コード長 2,026 bytes
コンパイル時間 3,770 ms
コンパイル使用メモリ 78,952 KB
実行使用メモリ 109,340 KB
最終ジャッジ日時 2024-12-14 14:22:52
合計ジャッジ時間 6,830 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

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();
precalc();
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(slow(A, B, C));
System.out.println(solve(A, B, C));
}
}
}
final int mod = 2<<20;
final long[] factFactor2 = new long[mod];
final long[] factMod1048576 = new long[mod];
void precalc() {
factMod1048576[0] = 1;
for (int i = 1; i < mod; i++) {
int j, factor2 = 0;
for (j = i; j % 2 == 0; j /= 2) factor2++;
factMod1048576[i] = factMod1048576[i-1] * j % mod;
factFactor2[i] = factFactor2[i-1] + factor2;
}
}
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 = factMod1048576[n+r-1] * modInverse(factMod1048576[r], mod) % mod * modInverse(factMod1048576[n-1], mod) % 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