「FPS 24 題」全部解く: L「順列 2」

解きます

解く

順列のFunctional Graphは「いくつかのループ」の形になることが知られています.
その前提で制約を見ると「2つ以下の要素しか無いループが無い」と言い換えられます.

とりあえず$a_n$を長さ$n$の条件を満たす順列の個数として漸化式を立てます. 条件を満たす順列のFunctional Graphから, 1つループを選んでそれを消すと, より小さい条件を満たす順列になります. 消すループの選び方は「一番左の要素を含むループ」とかで決めてやります. すると
$$a_n=\sum_{i=3}^{n}\frac{\left(n-1\right)!}{\left(n-i\right)!}a_{n-i}$$
という式が立ちます. シグマの中が「$i$個の要素からなるループを消したときの順列の個数」です. $i=3$から始めることで2以下のループを除外します.

指数型母関数にしたい見た目をしてるので$b_n=a_n/n!$として整えると
$$\begin{align}
b_n
&=\frac{\left(n-1\right)!}{n!}\sum_{i=3}^{n}b_{n-i} \\
&=\frac 1n\sum_{i=3}^{n}b_{n-i} \\
&=\frac 1n\sum_{i=0}^{n-3}b_{i} \\
\end{align}$$
と, 簡単な形になります.
FPSにしましょう.
$$\begin{align}
f=\sum_{n=0}^\infty b_n x^n
&=\sum_{n=0}^\infty\frac{x^n}n\sum_{i=0}^{n-3}b_i \\
&=\sum_{i=0}^\infty b_i\sum_{n=i+3}^\infty\frac{x^n}n \\
\end{align}$$
$x^n/n$は$\int x^{n-1}\mathrm dx$と書き換えられます.
$$\begin{align}
f &=\sum_{i=0}^\infty b_i\sum_{n=i+3}^\infty\int x^{n-1}\mathrm dx \\
&=\sum_{i=0}^\infty b_i\sum_{n=i+2}^\infty\int x^n\mathrm dx \\
&=\int\sum_{i=0}^\infty b_i\sum_{n=i+2}^\infty x^n\mathrm dx \\
&=\int\sum_{i=0}^\infty b_i x^i\sum_{n=2}^\infty x^n\mathrm dx \\
&=\int f\frac{x^2}{1-x}\mathrm dx \\
\end{align}$$
微分方程式になりました. 変数分離形ってやつですね.
$$\begin{align}
\frac{\mathrm df}{\mathrm dx} &= f\frac{x^2}{1-x} \\
\frac{\mathrm df/\mathrm dx}f &= \frac{x^2}{1-x} \\
\int\frac{\mathrm df/\mathrm dx}f\mathrm dx &= \int\frac{x^2}{1-x}\mathrm dx \\
\int\frac{\mathrm df}f &= \int\frac{x^2}{1-x}\mathrm dx \\
\log f &= -x-\frac{x^2}2-\log\left(1-x\right) + C \\
f &= \frac{e^{-x-\frac{x^2}2}}{1-x}e^C \\
\end{align}$$
$f$の定数項$b_0$は$1$なので, 定数$C=0$です. これで目的の関数が求まりました.

指数の上に乗っている$-x-\frac{x^2}2$は疎なFPSなので, 線形時間で計算できます.
$g=e^{-x-\frac{x^2}2}$として微分して様子を見ると,
$$\begin{align}
\frac{\mathrm dg}{\mathrm dx}=\left(-1-x\right)g
\left[x^k\right]\frac{\mathrm dg}{\mathrm dx}&=\left[x^k\right]\left(-1-x\right)g \\
\left(k+1\right)\left[x^{k+1}\right]g&=-\left[x^k\right]g-\left[x^{k-1}\right]g \\
\end{align}$$
つまり
$$\left[x^n\right]g=-\frac{\left[x^{n-1}\right]g+\left[x^{n-2}\right]g}n$$
という漸化式になりました. 小さい項は$\left[x^0\right]g=1, \left[x^1\right]g=-1$なので, これで$g$が計算できるようになりました.

これをを$1-x$で割れば答えですが, $1-x$で割るのは単に累積和するということなので, これで全体で$O\left(N\right)$です

use ac_library::*;
use proconio::*;

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
    }
    // [x^0]g = 1, [x^1]g = -1
    let mut g = vec![Mint::raw(1), -Mint::raw(1)];
    // 漸化式を回す
    for i in 2..=n {
        g.push(-(g[i - 2] + g[i - 1]) / i);
    }
    // 累積和する
    let mut ans = Mint::raw(0);
    for i in 0..=n {
        ans += g[i];
    }
    // 指数型母関数だったので, n!をかける
    for i in 1..=n {
        ans *= i;
    }
    println!("{ans}");
}

提出(31 ms):

終わり

ついに微分方程式が出てきましたね
以上です