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