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

解きます

解く

答えを$a_N$と書くことにします. この問題の順列が「条件を満たさない」というのは「真接頭辞が順列になるものがある」, 更に「真接頭辞が条件を満たす順列になるものがある」と言い換えられます.
長さ$N$の順列は$N!$個あるので, この言い換えを基に,
$$a_N = N! - \sum_{k=1}^{N-1} a_k(N-k)!$$
のような漸化式が立ちます. これをFPSにしましょう.

$$\begin{align}
f &= \sum_{i=1}^\infty a_i x^i \\
&= \sum_{i=1}^\infty x^i\left(i!-\sum_{j=1}^{i-1} a_j(i-j)!\right) \\
&= \sum_{i=1}^\infty x^ii! - \sum_{j=1}^\infty a_j\sum_{i=j+1}^\infty x^i(i-j)! \\
&= \sum_{i=1}^\infty x^ii! - \sum_{j=1}^\infty a_jx^j\sum_{i=1}^\infty x^ii! \\
&= \sum_{i=1}^\infty x^ii! - f\sum_{i=1}^\infty x^ii! \\
\end{align}$$
$g=\sum_{i=1}^\infty x^ii!$と置いて, 求めるべきものは
$$\begin{align}
f &= g - f g \\
\left(1+g\right)f &= g \\
f &= \frac g{1+g} \\
&= 1-\frac 1{1+g} \\
\end{align}$$
と分かりました. 昨日と同じニュートン法で$O\left(N\log N\right)$で解けますね.

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

type Mint = ModInt998244353;

fn main() {
    input! {
        n: usize,
    }

    // h = 1+g
    let mut h = vec![Mint::raw(1)];
    for i in 1..(n + 1).next_power_of_two() {
        h.push(h[i - 1] * i);
    }

    // ニュートン法で逆数を求める
    let mut f = vec![Mint::raw(1)];
    while f.len() < h.len() {
        let m = convolution(&f, &f);
        let m = convolution(&m, &h[..f.len() * 2]);
        f.extend((0..f.len()).map(|_| Mint::raw(0)));
        for i in 0..f.len() {
            f[i] = f[i] * 2 - m[i];
        }
    }
    // 1から引いたもの(n=0のケースは与えられないので単に符号反転すればいい)が答え
    println!("{}", -f[n]);
}

提出(108 ms):

終わり

ここの$g$は$x$が実数なら$x=0$のとき以外発散しちゃうんですが, こういうの考えてもいいんですね
以上です