189462025-11-12 20:42:31algoproPermutációkcpp17Elfogadva 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";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Elfogadva17ms16436 KiB
subtask212/12
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms508 KiB
subtask311/11
8Elfogadva50ms35892 KiB
9Elfogadva43ms35816 KiB
10Elfogadva35ms35908 KiB
11Elfogadva50ms35732 KiB
subtask423/23
12Elfogadva1ms508 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
subtask519/19
17Elfogadva2ms564 KiB
18Elfogadva1ms564 KiB
19Elfogadva2ms756 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
subtask635/35
22Elfogadva41ms35892 KiB
23Elfogadva35ms35708 KiB
24Elfogadva35ms35864 KiB
25Elfogadva50ms35892 KiB
26Elfogadva64ms33844 KiB
27Elfogadva1ms500 KiB
28Elfogadva59ms35892 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB