結果
問題 | No.474 色塗り2 |
ユーザー |
|
提出日時 | 2016-12-27 20:24:01 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,485 ms / 2,000 ms |
コード長 | 1,463 bytes |
コンパイル時間 | 3,919 ms |
コンパイル使用メモリ | 86,132 KB |
実行使用メモリ | 130,352 KB |
最終ジャッジ日時 | 2025-01-24 10:00:22 |
合計ジャッジ時間 | 7,375 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
package yukicoder;import java.util.*;public class Q474 {static class Int {long v = 0;long c = 0;public Int(long n) {while (n % 2 == 0) {n /= 2;++c;}this.v = n;}public Int() {}Int mul(Int o) {Int i = new Int();i.c = this.c + o.c;i.v = this.v * o.v % mod;return i;}Int divide(Int o) {Int i = new Int();i.c = this.c - o.c;i.v = this.v * pow(o.v, mod / 2 - 1) % mod;return i;}long toLong() {long v = 1l << c;v = (v * this.v) % mod;return v;}}final static long mod = 1 << 20;public static void main(String[] args) {Int[] fac = new Int[2000001];fac[0] = new Int(1);for (int i = 1; i < fac.length; ++i) {fac[i] = fac[i - 1].mul(new Int(i));}Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();if (c % 2 == 0) {System.out.println("0");continue;}Int x = (new Int(c)).mul(fac[c + b - 1]).divide(fac[b]).divide(fac[c - 1]);if (((x.toLong() + a - 1) & a) == a) {System.out.println("1");} else {System.out.println("0");}}}static long pow(long a, long n) {long ret = 1;for (; n > 0; n >>= 1, a = (a * a) % mod) {if (n % 2 == 1)ret = (ret * a) % mod;}return ret;}static void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}