mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 009 C - 高橋君、24歳

解法

「0 から K-1 がバラバラ, 残りは揃っている」の場合の数が分かれば, 後は答えを comb[N][K] 倍するだけです。comb[N][K] はおよそ O(K log K) で求めることができるので, 問題は「」の中身の場合の数です。

これは, 包除原理で求めることが出来ます。
0 個以上重なっているのがある場合の数は K! 通り,
1 個以上重なっているのがある場合の数は comb[K][1] * (K-1)! = K! 通り,
2 個以上重なっているのがある場合の数は comb[K][2] * (K-2)! = K!/2! 通り,
3 個以上重なっているのがある場合の数は comb[K][3] * (K-3)! = K!/3! 通り, ...

と続きます。答えは K! - K! + K!/2! - K!/3! + ... となるので, これを計算しましょう。

typedef unsigned long long ull;

const ull MOD = 1777777777;

ull mod_pow(ull x, ull p, ull MOD) {
    ull a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ull mod_inverse(ull a, ull m) {
    return mod_pow(a, MOD-2, m);
}

ull nCr(ull n, ull r) {
    ull ret = 1;
    for (ull i = 0; i < r; i++) (ret *= (n-i)%MOD) %= MOD;
    for (ull i = 1; i <= r; i++) (ret *= mod_inverse(i, MOD)) %= MOD;
    return ret;
}

ull calc(ull K) {
    ull p = 1;
    for (ull i = 1; i <= K; i++) (p *= i) %= MOD;
    ull ret = 0;
    for (ull i = 2; i <= K; i++) {
        (p *= mod_inverse(i, MOD)) %= MOD;
        if (i%2==0) (ret += p) %= MOD;
        else (ret += MOD-p) %= MOD;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ull N, K;
    cin >> N >> K;
    ull ans = calc(K);
    (ans *= nCr(N, K)) %= MOD;
    cout << ans << endl;
    return 0;
}