結果

問題 No.117 組み合わせの数
ユーザー nebukuro09nebukuro09
提出日時 2019-08-23 11:07:06
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 128 ms / 5,000 ms
コード長 2,554 bytes
コンパイル時間 1,547 ms
コンパイル使用メモリ 149,784 KB
実行使用メモリ 12,668 KB
最終ジャッジ日時 2024-06-22 02:23:18
合計ジャッジ時間 2,473 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 128 ms
12,668 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

immutable long MAX = 2*10^^6+1;
immutable uint MOD = 10^^9 + 7;
alias mint = ModInt!MOD;

void main() {
    auto f = new mint[](MAX);
    f[0] = f[1] = mint(1);

    foreach(i; 2..MAX) {
        f[i] = f[i-1] * i;
    }

    int T, N, K;
    char CPH;
    scanf("%d\n", &T);

    foreach(i; 0..T) {
        scanf("%c(%d,%d)\n", &CPH, &N, &K);
        if (CPH == 'C') {
            if (N < K) {writeln(0); continue;}
            writeln(f[N] / f[N-K] / f[K]);
        }
        else if (CPH == 'P') {
            if (N < K) {writeln(0); continue;}
            writeln(f[N] / f[N-K]);
        }
        else {
            if (N == 0 && K == 0) {writeln(1); continue;}
            if (N == 0) {writeln(0); continue;}
            writeln(f[N+K-1] / f[N-1] / f[K]);
        }
    }
}

struct ModInt(uint mod) {
    import std.conv : to;

    uint n;

    this(int n) {
        this.n = (n % mod + mod) % mod;
    }

    this(long n) {
        this.n = (n % mod + mod) % mod;
    }

    private this(uint n) {
        this.n = n;
    }

    string toString() {
        return to!string(this.n);
    }

    private uint normilize(uint n) const {
        return n < mod ? n : n - mod;
    }

    private ModInt pow(uint n, long x) const {
        long ret = 1;
        long a = n;
        while (x) {
            if (x & 1) ret = ret * a % mod;
            a = a * a % mod;
            x >>= 1;
        }
        return ModInt(to!ulong(ret));
    }

    ModInt opBinary(string op : "+")(ModInt rhs) const {
        return ModInt(normilize(n + rhs.n));
    }

    ModInt opBinary(string op : "-")(ModInt rhs) const {
        return ModInt(normilize(n + mod - rhs.n));
    }

    ModInt opBinary(string op : "*")(ModInt rhs) const {
        return ModInt(to!uint(to!long(n) * rhs.n % mod));
    }

    ModInt opBinary(string op : "/")(ModInt rhs) const {
        return this * pow(rhs.n, mod-2);
    }

    ModInt opBinary(string op : "^^")(ModInt rhs) const {
        return pow(this.n, rhs.n);
    }

    ModInt opBinary(string op, T)(T rhs) {
        ModInt mod_rhs = ModInt(rhs);
        return opBinary!op(mod_rhs);
    }

    ModInt opOpAssign(string op)(ModInt rhs) {
        return mixin ("this=this"~op~"rhs");
    }

    ModInt opOpAssign(string op, T)(T rhs) {
        ModInt mod_rhs = ModInt(rhs);
        return mixin ("this=this"~op~"mod_rhs");
    }
}
0