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

問題

　人のうち人へ手紙を配り間違えたとき、あり得る配り方の組み合わせの数を求めよ。

解法

　まず人の中から配り間違えた人を選ぶ方法が。

　そして人に対して全て間違った配り方となる組み合わせの数は攪乱順列、あるいはモンモール問題などと言われるものであり、これは第項目をとして$$a_n = (n - 1)(a_{n - 1} + a_{n - 2})$$という漸化式が成り立つ。

　これらを掛け合わせたものが答えとなる。

反省

　23分48秒でAC。人について自分以外というのは有名問題のやつだなということに気が付き、式を考えるのが面倒だったので「プレゼント 自分以外 配り方」などとググってこれやこれといったページを見てそのまま書いた。

　N自体が大きいのでMODを取る必要があったり、攪乱順列の組み合わせ数を求める際の配列を小さくとりすぎていたりで2WA。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

const ll MOD = 1777777777;

ll POW(ll n, ll m) {
    ll result = 1;
    while (m) {
        if (m & 1) {
            result *= n;
            result %= MOD;
        }

        n *= n;
        n %= MOD;
        m /= 2;
    }

    return result;
}

ll combination(ll n, ll m) {
    ll result = 1;
    for (ll i = 1; i <= m; i++) {
        result *= (n - i + 1) % MOD;
        result %= MOD;
        result *= POW(i, MOD - 2);
        result %= MOD;
    }
    return result;
}

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> f(max(K + 1, (ll)4));
    f[2] = 1;
    f[3] = 2;
    for (ll i = 4; i <= K; i++) {
        f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % MOD;
    }
    cout << (combination(N, K) * f[K] % MOD) << endl;
}