Single Round Match 798 Med - ExpectedValue

線形解法がおもったより単純だった

解法

(swap数の総和) / (完全順列の数) を求める問題である

s _ i := i 個の要素の完全順列の数

とすると，これは有名らしく，

s _ i = (i - 1) * (s _ {i - 1} + s _ {i - 2})

で線形で求まる．

swap数は i \rightarrow a _ {i}に辺を貼った時の (サイクル長 - 1) だけかかる

サイクル長 c となる，要素の選び方が \displaystyle \binom{N}{c} でこれの並び方が (c - 1)! で，残りの N - c 個が完全順列となることを考えると，これが全体の総和に与える寄与は

\displaystyle (c - 1) * \binom{N}{c} * (c - 1)! * s _ {N-c}

となり全てのサイクル長について考えたらいい．

提出コード

struct  ExpectedValue {
    int solve(int N) {
        COMinit();
        vector<mint> subfactorial(N + 1);
        subfactorial[0] = 1;
        subfactorial[1] = 0;
        for (int i = 2; i <= N; i++) {
            subfactorial[i] = mint(i - 1) * (subfactorial[i - 1] + subfactorial[i - 2]);
        }
        mint res = 0;
        for (int cyc = 2; cyc <= N; cyc++) {
            res += mint(cyc - 1) * COM(N, cyc) * fac[cyc - 1] * subfactorial[N - cyc];
        }
        res /= subfactorial[N];
        return (int)res.x;
    }
};