189452025-11-12 20:41:39algoproPermutációkcpp17Wrong answer 23/10059ms35924 KiB
// UUID: b3953903-8e5b-4112-81e3-37933b5caec6
#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;
		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
3Accepted18ms16516 KiB
subtask212/12
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask311/11
8Accepted43ms35892 KiB
9Accepted48ms35660 KiB
10Accepted35ms35892 KiB
11Accepted50ms35804 KiB
subtask40/23
12Accepted1ms508 KiB
13Accepted1ms316 KiB
14Accepted1ms508 KiB
15Accepted1ms316 KiB
16Wrong answer1ms316 KiB
subtask50/19
17Accepted2ms564 KiB
18Accepted1ms564 KiB
19Accepted1ms564 KiB
20Wrong answer1ms316 KiB
21Wrong answer1ms316 KiB
subtask60/35
22Accepted41ms35848 KiB
23Accepted35ms35748 KiB
24Accepted35ms35872 KiB
25Accepted50ms35692 KiB
26Accepted59ms33844 KiB
27Wrong answer1ms316 KiB
28Accepted52ms35924 KiB
29Wrong answer1ms316 KiB
30Accepted1ms316 KiB