結果

問題 No.474 色塗り２
ユーザー yosupotyosupot
提出日時 2016-12-24 13:56:02
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 127 ms / 2,000 ms
コード長 3,483 bytes
コンパイル時間 698 ms
コンパイル使用メモリ 110,660 KB
実行使用メモリ 35,712 KB
最終ジャッジ日時 2024-06-12 06:02:40
合計ジャッジ時間 1,445 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
28,092 KB
testcase_01 AC 23 ms
29,240 KB
testcase_02 AC 24 ms
29,064 KB
testcase_03 AC 127 ms
35,712 KB
testcase_04 AC 24 ms
29,172 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/+ dub.sdl:
	name "A"
	dependency "dcomp" version="0.0.1"
+/
import std.stdio, std.conv;
import std.algorithm, std.range, std.random;
import std.string, std.array, std.container, std.bigint;
import core.bitop;

// import dcomp.scanner;
// import dcomp.numeric;

Scanner sc;
static this() {
    sc = new Scanner();
}

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

alias Mint = ModInt!(MD);

int[] p2c;
Mint[] fact, iFac;
static this() {
    p2c = new int[MN];
    fact = new Mint[MN];
    iFac = new Mint[MN];

    p2c[0] = 0;
    fact[0] = Mint(1);
    foreach (i; 1..MN) {
        p2c[i] = p2c[i-1]+i.bsf;
        fact[i] = fact[i-1]*Mint(i>>i.bsf);
    }
    iFac[MN-1] = Mint(1)/fact[MN-1];
    foreach_reverse (i; 0..MN-1) {
        iFac[i] = iFac[i+1]*Mint((i+1)>>(i+1).bsf);
    }
}

int main() {
    int T;

    sc.read(T);
    foreach (_; 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)*Mint(1<<two);

            if (~((up.v+A-1)%MD) & A) {
                return 0;
            }
            return 1;
        }
        writeln(check());
    }
    return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

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;
    }
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/numeric.d */
// module dcomp.numeric;

T lcm(T)(const T a, const T b) {
    import std.numeric : gcd, abs;
    return a / gcd(a,b) * b;
}

//T[0] = a*T[1]+b*T[2], T[0]=gcd
T[3] extGcd(T)(T a, T b) {
    if (b==0) {
        return [a, 1, 0];
    } else {
        auto e = extGcd(b, a%b);
        return [e[0], e[2], e[1]-a/b*e[2]];
    }
}

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 opBinary(string op:"/")(ModInt r) {return this*inv(r);}
    auto opOpAssign(string op)(ModInt r) {return mixin ("this=this"~op~"r");}
    static ModInt inv(ModInt x) {return ModInt(extGcd(x.v, MD)[1]);}
    string toString() {return v.to!string;}
}
0