189462025-11-12 20:42:31algoproPermutációkcpp17Accepted 100/10064ms35908 KiB
// UUID: cf197e5b-837d-4560-98a1-0cf652d4fd07
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
using ll = long long;
int main() {
	int n, k;
	cin >> n >> k;
	if(k >= n)
	{
		ll x = 1;
		for(int i = 1; i <= n; i++)
		{
			x *= i;
			x %= MOD;
		}
		cout << x << "\n";
		return 0;
	}
	vector<vector<int> > pa(n + 5, vector<int>(n + 5));
	pa[0][0] = 1;
	for(int i = 1; i < n + 5; i++)
	{
		pa[i][0] = 1;
		for(int j = 1; j <= i; j++)
		{
			pa[i][j] = (pa[i - 1][j - 1] + pa[i - 1][j]) % MOD;
		}
	}
	int s = n - k;
	vector<ll> dp(n + 1);
	vector<ll> ba(n + 1);
	dp[0] = 1;
	vector<ll> fac(n + 1);
	fac[0] = 1;
	for(int i = 1; i <= n; i++)
	{
		fac[i] = fac[i - 1] * i;
		fac[i] %= MOD;
		dp[i] = fac[i];
		//if(i < s) continue;
		for(int l = s; l + 1 <= i; l += s)
		{
			ll val = dp[i - l - 1] * pa[i][l + 1];
			val %= MOD;
			val *= l;
			val %= MOD;
			ba[i] += val;
			ba[i] %= MOD;
		}
		for(int l = s; l <= i; l += s)
		{
			dp[i] -= dp[i - l] * pa[i][l];
			dp[i] %= MOD;
		}
		for(int j = i; j >= s + 1; j--)
		{
			ll val = ba[j];
			val *= pa[i][i - j];
			val %= MOD;
			val *= fac[i - j];
			val %= MOD;
			dp[i] -= val;
			dp[i] %= MOD;
		}
		//cout << dp[i] << " ";
	}
	cout << (((fac[n] - dp[n]) % MOD) + MOD) % MOD << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
3Accepted17ms16436 KiB
subtask212/12
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms508 KiB
subtask311/11
8Accepted50ms35892 KiB
9Accepted43ms35816 KiB
10Accepted35ms35908 KiB
11Accepted50ms35732 KiB
subtask423/23
12Accepted1ms508 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
subtask519/19
17Accepted2ms564 KiB
18Accepted1ms564 KiB
19Accepted2ms756 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
subtask635/35
22Accepted41ms35892 KiB
23Accepted35ms35708 KiB
24Accepted35ms35864 KiB
25Accepted50ms35892 KiB
26Accepted64ms33844 KiB
27Accepted1ms500 KiB
28Accepted59ms35892 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB