189442025-11-12 20:38:30algoproPermutációkcpp17Futási hiba 11/1003.101s36084 KiB
// UUID: 8acf5147-54d2-43ec-8bcb-356df82f24bb
#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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Elfogadva17ms16436 KiB
subtask20/12
4Elfogadva1ms316 KiB
5Elfogadva1ms500 KiB
6Futási hiba1ms512 KiB
7Elfogadva1ms316 KiB
subtask311/11
8Elfogadva50ms35892 KiB
9Elfogadva43ms35636 KiB
10Elfogadva43ms35896 KiB
11Elfogadva43ms35636 KiB
subtask40/23
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms508 KiB
16Futási hiba1ms316 KiB
subtask50/19
17Elfogadva2ms564 KiB
18Elfogadva2ms564 KiB
19Elfogadva2ms760 KiB
20Futási hiba2ms820 KiB
21Futási hiba1ms684 KiB
subtask60/35
22Elfogadva37ms35840 KiB
23Elfogadva35ms36084 KiB
24Elfogadva41ms35892 KiB
25Elfogadva50ms35892 KiB
26Elfogadva67ms33844 KiB
27Futási hiba32ms26676 KiB
28Elfogadva52ms35720 KiB
29Időlimit túllépés3.101s35892 KiB
30Futási hiba1ms316 KiB