結果
問題 | No.474 色塗り2 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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 debugstatic void dump(Object... o) {System.err.println(Arrays.deepToString(o));}}