ARC009 C問題：高橋君，24歳 - 忘れても大丈夫

問題. 高橋君，24歳

写像 $f \colon N \to N$ で $\left| \{i \in N \mid f(i) = i \} \right| = n - k$ となるものが何通りあるかを $1,777,777,777$ （素数）で割った余りで答えよ．ただし， $N = \{1, 2, \ldots, n\}$ とする．

制約： $2 \le n \le 777,777,777,777,777,777$ ，　 $2 \le k \le 777,777$

解法．包除原理

$K = \{1, 2, \ldots, k \}$ とする． $m$ をどの要素の値も自分自身とならない始域と終域が $K$ の写像全体の個数とする．このとき，求める答えは
　　 $\binom{n}{n - k} \times m$
となる． $\binom{n}{n - k}$ は要素の値が自分自身となる要素の選び方である．

$A_i$ を要素 $i$ の値が自分自身となる写像全体（始域と終域が $K$ ）とすると包除原理から，
　　 $m = \sum_{X \subseteq K} (-1)^{|X|} \left| \cap_{i \in X} A_i \right|$
となる．ここで， $|X| = j$ のとき $\left| \cap_{i \in X} A_i \right | = (k - j)!$ となるので，
　　 $m = \sum_{i = 0}^{k} (-1)^i \binom{k}{i} (k - i)! = k! \sum_{i = 0}^{k} \frac{(-1)^i}{i!}$
となる．したがって，
　　 $\binom{n}{n - k} \times m = \frac{n!}{(n - k)!} \left( \sum_{i=0}^{k} \frac{(-1)^i}{i!} \right)$
となり， $\binom{n}{n - k} = n (n - 1) (n - 2) \cdots (n - k + 1)$ から $k$ 個の積となり，二項目も $k$ 個の和なので $O(K)$ 時間で答えが求まる．

計算時間： $O(K)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

template<typename T, T MOD>
struct ModType {
public:
    using Int = T;

    ModType(long long _v = 0) : v(set(_v)) {}
    ModType(const ModType &r) : v(set(r.v)) {}

    Int get_val() const { return v; }

    bool operator<(ModType r) const { return v < r.v; }
    bool operator>(ModType r) const { return v > r.v; }
    bool operator<=(ModType r) const { return v <= r.v; }
    bool operator>=(ModType r) const { return v >= r.v; }
    bool operator==(ModType r) const { return v == r.v; }
    bool operator!= (ModType r) const { return v != r.v; }

    ModType operator-() const { return ModInt(v ? mod - v : v); }
    ModType &operator=(const ModType &r) { if (this != &r) v = set(r.v); return *this; }

    ModType operator++(){ if (++v == mod) v = 0; return *this; }
    ModType operator--(){ v = (v == 0 ? mod - 1 : v - 1); return *this; }

    ModType &operator+=(ModType r) { (v += r.v) %= mod; return *this; }
    ModType &operator-=(ModType r) { (v -= r.v - mod) %= mod; return *this; }
    // ModType &operator*=(ModType r) { v = (__uint128_t(v) * r.v) % mod; return *this; }
    ModType &operator*=(ModType r) { v = 1ULL * v * r.v % mod; return *this; }
    ModType &operator/=(ModType r) { *this *= r.inv(); return *this; }

    ModType operator+(ModType r) const { return ModType(*this) += r; }
    ModType operator-(ModType r) const { return ModType(*this) -= r; }
    ModType operator*(ModType r) const { return ModType(*this) *= r; }
    ModType operator/(ModType r) const { return ModType(*this) /= r; }

    ModType inv() const {
        long long a = v, b = mod, u = 1, w = 0;
        while (b) {
            long long t = a / b;
            std::swap(a -= t * b, b);
            std::swap(u -= t * w, w);
        }
        return ModType(u);
    }

    ModType pow(Int e) {
        ModType a = *this, x(1);
        for ( ; 0 < e; e >>= 1) { if (e & 1) x *= a; a *= a; }
        return x;
    }
    inline ModType pow(ModType &e) { return pow(e.v); }

    friend std::ostream &operator<<(std::ostream &os, const ModType &r) { return os << r.v; }
    friend std::istream &operator>>(std::istream &is, ModType &r) {
        is >> r.v; r.set();return is;
    }

    static std::vector<ModType> Inverse(const Int n = mod - 1) {
        std::vector<ModType> inv(n + 1);
        inv[1].v = 1;
        for (Int a = 2; a <= n; ++a)
            inv[a] = inv[mod % a] * T(mod - mod / a);
        return inv;
    }

private:
    static constexpr Int mod = MOD;
    Int v;

    inline static Int set(const Int x) { return x < 0 ? (x % mod) + mod : x % mod; }
    inline void set() { v = set(v); }
};

using ModInt = ModType<ll, 1777777777>;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    ll n, k;
    cin >> n >> k;

    ModInt sum(0), p(1);
    for (ll i = 2; i <= k; ++i) {
        p *= i;
        if (i & 1) sum -= p.inv();
        else sum += p.inv();
    }
    ModInt f(1);
    for (ll i = 0; i < k; ++i)
        f *= ModInt(n - i);

    cout << f * sum << endl;

    return 0;
}

剰数が見慣れない素数だったので，そこにポイントがあるかなと思いながら式変形をしたらポイントは $k$ だった．ある条件を満たす写像の個数はよく研究されているからググればあるんだろうなと思って後で調べたら高校数学だった．
　攪乱順列の公式 | 高校数学の美しい物語