每日一题Day4

题解：

还是太年轻了QAQ不知道这个OEIS是啥....
先手推一下前5项：

$dp[1] = 0$
$dp[2] = 1$
$dp[3] = 1$
$dp[4] = 6$
$dp[5] = 22$

然后放进OEIS里就有了这么一个公式： $a_n = (n - 1) * (a_{n - 1} + a_{n - 2}) - \frac{(n - 1) * (n - 2) * a_{n - 3}}{2}$
注意最后我们的 $dp[n]$ 要写成 $(dp[n] + m) \mod m$

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
#define rep(i,a,b) for(int i = a;i <= b;i ++)
#define esp 1e-16

using namespace std;

const int maxn = 2e5 + 19;

ll n, m;
ll dp[maxn] = {};

void init()
{
    dp[1] = 0;
    dp[2] = 1;
    dp[3] = 1;
}

int main()
{
    while (cin >> n >> m) {
        init();
        for (ll i = 4ll; i <= n; i++) dp[i] = ((i - 1) * dp[i - 1] + (i - 1) * dp[i - 2] - (i - 1) * (i - 2) / 2 * dp[i - 3]) % m;
        cout << (dp[n] + m) % m << endl;
    }
    return 0;
}