(Easy) Library Checker - Montmort Number

原题链接：https://judge.yosupo.jp/problem/montmort_number_mod

Montmort Number

Let $a_k$ be the number of size $k$ permutations $p$ s.t. $p_i \ne i$ for each $i$.
Given $N,M$. For each $i=1,⋯,N$, print $b_k=a_k\mod M$.

Constraints

$1\le N \le 10^6$

$1\le M \le 10^9$

Input

N M

Output

$b_1 \ b_2\ ...\ b_n$

Sample

#1

10 100
0 1 2 9 44 65 54 33 96 61

#2

20 998244353
0 1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 294304226 127281753 910981941 600290115 222488424 11814221 224470198 496426549

题目描述

设$1...k$共$k$个数，排列这$k$个数，共有$k!$中可能，设其中一种排列为$p$，$p_i$表示第$i$个数的值，$a_k$表示满足所有$i$的情况下$p_i \ne i$的排列的个数；

例如：$k=2$，共有$2!=2$种排列，分别为$\{1,2\}$，$\{2,1\}$，满足$p_i \ne i$的排列只有一种，即$\{2,1\}$

输入$N,M$，对于每一个$k=1,⋯,N$，求$a_k \mod M$的值

解决方案

$a_0=1$，我的理解是，没有东西可以排列的情况有1种，即$\{\}$

$a_1=0$，只有$\{1\}$一种排列，该排列不满足$p_i \ne i$

对于$a_k$来说，第1个位置的数有$k-1$种可能（即$2,3,...,k$之一），假设把$i$放在第1个位置，这时有2种选择

1. 把1放到第$i$个位置，这时剩下的$k-2$个位置分别都存在对应的数字，成为了一个子问题，即$a_{k-2}$
2. 1不放到第$i$个位置，这样便相当于1不能放在第$i$个位置，相当于一个$k-1$个数的子问题，即$a_{k-1}$

因此

$$\left\{ \begin{array}{lr} a_0=1 , \\ a_1=0 , \\ a_k=(k-1)*(a_{k-1}+a_{k-2}) , & k\ge 2 \end{array} \right.$$

时间复杂度

$O(n)$

代码

#include <iostream>

int main() {
    int n,m;
    while(cin>>n>>m) {
        vi f(n+1, 0);
        a[0] = 1; a[1] = 0;
        cout << 0;
        rep(k,2,n+1) {
            a[k] = ((ll)(k-1) * (a[k-1] + a[k-2])) % m;
            cout << " " << f[k];
        }
        cout << endl;
    }
}