| 18946 | 2025-11-12 20:42:31 | algopro | Permutációk | cpp17 | Accepted 100/100 | 64ms | 35908 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";
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 1ms | 316 KiB | ||||
| 2 | Accepted | 1ms | 316 KiB | ||||
| 3 | Accepted | 17ms | 16436 KiB | ||||
| subtask2 | 12/12 | ||||||
| 4 | Accepted | 1ms | 316 KiB | ||||
| 5 | Accepted | 1ms | 316 KiB | ||||
| 6 | Accepted | 1ms | 316 KiB | ||||
| 7 | Accepted | 1ms | 508 KiB | ||||
| subtask3 | 11/11 | ||||||
| 8 | Accepted | 50ms | 35892 KiB | ||||
| 9 | Accepted | 43ms | 35816 KiB | ||||
| 10 | Accepted | 35ms | 35908 KiB | ||||
| 11 | Accepted | 50ms | 35732 KiB | ||||
| subtask4 | 23/23 | ||||||
| 12 | Accepted | 1ms | 508 KiB | ||||
| 13 | Accepted | 1ms | 316 KiB | ||||
| 14 | Accepted | 1ms | 316 KiB | ||||
| 15 | Accepted | 1ms | 316 KiB | ||||
| 16 | Accepted | 1ms | 316 KiB | ||||
| subtask5 | 19/19 | ||||||
| 17 | Accepted | 2ms | 564 KiB | ||||
| 18 | Accepted | 1ms | 564 KiB | ||||
| 19 | Accepted | 2ms | 756 KiB | ||||
| 20 | Accepted | 1ms | 316 KiB | ||||
| 21 | Accepted | 1ms | 316 KiB | ||||
| subtask6 | 35/35 | ||||||
| 22 | Accepted | 41ms | 35892 KiB | ||||
| 23 | Accepted | 35ms | 35708 KiB | ||||
| 24 | Accepted | 35ms | 35864 KiB | ||||
| 25 | Accepted | 50ms | 35892 KiB | ||||
| 26 | Accepted | 64ms | 33844 KiB | ||||
| 27 | Accepted | 1ms | 500 KiB | ||||
| 28 | Accepted | 59ms | 35892 KiB | ||||
| 29 | Accepted | 1ms | 316 KiB | ||||
| 30 | Accepted | 1ms | 316 KiB | ||||