[Boj 1947] 선물 전달

http://icpc.me/1947

1947번: 선물 전달

교란순열이다

dp[i] = (i-1) * (dp[i-1] + dp[i-2])

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MOD = 1e9;

int n;
ll dp[1000000 + 5];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	dp[2] = 1;
	for (int i = 3; i <= n; i++)
		dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD;
	cout << dp[n] << "\n";

	return 0;
}