| 18945 | 2025-11-12 20:41:39 | algopro | Permutációk | cpp17 | Hibás válasz 23/100 | 59ms | 35924 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";
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 316 KiB | ||||
| 2 | Elfogadva | 1ms | 316 KiB | ||||
| 3 | Elfogadva | 18ms | 16516 KiB | ||||
| subtask2 | 12/12 | ||||||
| 4 | Elfogadva | 1ms | 316 KiB | ||||
| 5 | Elfogadva | 1ms | 316 KiB | ||||
| 6 | Elfogadva | 1ms | 316 KiB | ||||
| 7 | Elfogadva | 1ms | 316 KiB | ||||
| subtask3 | 11/11 | ||||||
| 8 | Elfogadva | 43ms | 35892 KiB | ||||
| 9 | Elfogadva | 48ms | 35660 KiB | ||||
| 10 | Elfogadva | 35ms | 35892 KiB | ||||
| 11 | Elfogadva | 50ms | 35804 KiB | ||||
| subtask4 | 0/23 | ||||||
| 12 | Elfogadva | 1ms | 508 KiB | ||||
| 13 | Elfogadva | 1ms | 316 KiB | ||||
| 14 | Elfogadva | 1ms | 508 KiB | ||||
| 15 | Elfogadva | 1ms | 316 KiB | ||||
| 16 | Hibás válasz | 1ms | 316 KiB | ||||
| subtask5 | 0/19 | ||||||
| 17 | Elfogadva | 2ms | 564 KiB | ||||
| 18 | Elfogadva | 1ms | 564 KiB | ||||
| 19 | Elfogadva | 1ms | 564 KiB | ||||
| 20 | Hibás válasz | 1ms | 316 KiB | ||||
| 21 | Hibás válasz | 1ms | 316 KiB | ||||
| subtask6 | 0/35 | ||||||
| 22 | Elfogadva | 41ms | 35848 KiB | ||||
| 23 | Elfogadva | 35ms | 35748 KiB | ||||
| 24 | Elfogadva | 35ms | 35872 KiB | ||||
| 25 | Elfogadva | 50ms | 35692 KiB | ||||
| 26 | Elfogadva | 59ms | 33844 KiB | ||||
| 27 | Hibás válasz | 1ms | 316 KiB | ||||
| 28 | Elfogadva | 52ms | 35924 KiB | ||||
| 29 | Hibás válasz | 1ms | 316 KiB | ||||
| 30 | Elfogadva | 1ms | 316 KiB | ||||