結果

問題 No.474 色塗り２
ユーザー yosupotyosupot
提出日時 2016-12-24 00:34:59
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 727 ms / 2,000 ms
コード長 2,755 bytes
コンパイル時間 824 ms
コンパイル使用メモリ 110,464 KB
実行使用メモリ 31,616 KB
最終ジャッジ日時 2024-06-12 06:02:38
合計ジャッジ時間 5,355 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 615 ms
25,600 KB
testcase_01 AC 616 ms
25,600 KB
testcase_02 AC 608 ms
25,728 KB
testcase_03 AC 727 ms
31,616 KB
testcase_04 AC 610 ms
25,728 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.stdio, std.conv;
import std.algorithm, std.range, std.random;
import std.string, std.array, std.container, std.bigint;
import core.bitop;

struct EG { long g, x, y; };
EG extGcd(long a, long b) {
    if (b==0) {
		return EG(a, 1, 0);
    } else {
        auto e = extGcd(b, a%b);
		return EG(e.g, e.y, e.x-a/b*e.y);
    }
}

struct ModInt(uint MD) {
    import std.conv : to;
    uint v;
    this(int v) {this.v = (v%MD+MD)%MD;}
    this(long v) {this.v = (v%MD+MD)%MD;}
    auto normS(uint x) {return (x<MD)?x:x-MD;}
    auto make(uint x) {ModInt m; m.v = x; return m;}
    auto opBinary(string op:"+")(ModInt r) {return make(normS(v+r.v));}
    auto opBinary(string op:"-")(ModInt r) {return make(normS(v+MD-r.v));}
    auto opBinary(string op:"*")(ModInt r) {return make(cast(ulong)v*r.v%MD);}
    auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");}
	static ModInt inv(ModInt x) {return Mint(extGcd(x.v, MD).x);}
    string toString() {return v.to!string;}
}

class Scanner {
	import std.stdio : File, readln, stdin;
	import std.conv : to;
	import std.range : front, popFront, array, ElementType;
	import std.array : split;
	import std.traits : isSomeString, isDynamicArray;
	import std.algorithm : map;
	File f;
	this(File f = stdin) {
		this.f = f;
	}
	string[] buf;
	bool succ() {
		while (!buf.length) {
			if (f.eof) return false;
			buf = readln.split;
		}
		return true;
	}
	int read(Args...)(auto ref Args args) {
		foreach (i, ref v; args) {
			if (!succ()) return i;
			alias VT = typeof(v);
			static if (!isSomeString!VT && isDynamicArray!VT) {
				v = buf.map!(to!(ElementType!VT)).array;
				buf.length = 0;
			} else {
				v = buf.front.to!VT;
				buf.popFront();
			}
		}
		return args.length;
	}
}

Scanner sc;

const int MN = 2000100;
const int MD = 1<<20;

alias Mint = ModInt!(MD);

int[] p2c;
Mint[] fact, iFac;
static this() {
	sc = new Scanner();
	p2c = new int[MN];
	fact = new Mint[MN];
	p2c[0] = 0;
	fact[0] = Mint(1);
	foreach (i; 1..MN) {
		int u = bsf(i); //2をu個持っている
		p2c[i] = p2c[i-1]+u;
		fact[i] = fact[i-1]*Mint(i>>u);
	}
	iFac = new Mint[MN];
	foreach (i; 0..MN) {
		iFac[i] = Mint.inv(fact[i]);
	}
}




int main() {
	int T;
	sc.read(T);
	foreach (caseNum; 0..T) {
		int A, B, C;
		sc.read(A, B, C);
		int check() {
			if (C % 2 == 0) {
				return 0;
			}
			int X = B+C-1;
			int Y = B;
			int two = p2c[X]-p2c[Y]-p2c[X-Y];
			Mint up = fact[X]*iFac[Y]*iFac[X-Y]*Mint(C);

			int iup = cast(int)(cast(long)(up.v) << two % MD);
			iup = (iup + A-1) % MD;
			int idw = A;
//			writeln("XY ", X, " ", Y);
//			writeln("DB ", two, " ", iup, " ", idw);
//			writeln(~iup & idw);
			if (~iup & idw) {
				return 0;
			}
			return 1;
		}
		writeln(check());
	}
	return 0;
}
0