189432025-11-12 20:35:47algoproPermutációkcpp17Runtime error 11/1003.101s36084 KiB
// UUID: ade31c4e-afb5-4405-bb2c-7761a01b60ae
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
using ll = long long;
int main() {
	int n, k;
	cin >> n >> k;
	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
1Accepted1ms508 KiB
2Accepted1ms316 KiB
3Accepted16ms16436 KiB
subtask20/12
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Runtime error1ms564 KiB
7Accepted1ms316 KiB
subtask311/11
8Accepted43ms36084 KiB
9Accepted48ms35636 KiB
10Accepted41ms35904 KiB
11Accepted43ms35636 KiB
subtask40/23
12Accepted1ms316 KiB
13Accepted1ms496 KiB
14Accepted1ms316 KiB
15Accepted1ms328 KiB
16Runtime error1ms316 KiB
subtask50/19
17Accepted2ms564 KiB
18Accepted2ms564 KiB
19Accepted1ms564 KiB
20Runtime error2ms776 KiB
21Runtime error1ms640 KiB
subtask60/35
22Accepted37ms35892 KiB
23Accepted41ms35892 KiB
24Accepted41ms35748 KiB
25Accepted45ms36084 KiB
26Accepted65ms33740 KiB
27Runtime error26ms26668 KiB
28Accepted59ms35732 KiB
29Time limit exceeded3.101s35904 KiB
30Runtime error1ms500 KiB