結果

問題 No.117 組み合わせの数
ユーザー nebukuro09nebukuro09
提出日時 2019-11-16 14:07:05
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 134 ms / 5,000 ms
コード長 2,889 bytes
コンパイル時間 1,527 ms
コンパイル使用メモリ 147,908 KB
実行使用メモリ 12,080 KB
最終ジャッジ日時 2024-06-22 03:02:02
合計ジャッジ時間 2,393 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 134 ms
12,080 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 comb = new Combinations!MOD(MAX.to!int);

    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') {
            writeln(comb.nCr(N, K));
        }
        else if (CPH == 'P') {
            writeln(comb.nPr(N, K));
        }
        else {
            writeln(comb.nHr(N, 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");
    }
}

class Combinations(uint mod) {
    alias mint = ModInt!mod;
    mint[] f;

    this(int maxval) {
        f = new mint[](maxval);
        f[0] = f[1] = mint(1);
        foreach(i; 1..maxval-1) {
            f[i+1] = f[i] * (i+1);
        }
    }

    mint nCr(int n, int r) {
        if (n < r) return mint(0);
        return f[n] / f[n-r] / f[r];
    }

    mint nPr(int n, int r) {
        if (n < r) return mint(0);
        return f[n] / f[n-r];
    }

    mint nHr(int n, int r) {
        if (n == 0 &&r == 0) return mint(1);
        if (n == 0) return mint(0);
        return f[n+r-1] / f[n-1] / f[r];
    }
}
0