187512025-11-04 11:18:09algoproPermutációkcpp17Accepted 100/10065ms512 KiB
// UUID: 708a2b2e-48c1-4354-94dc-9b769051bdd3
#include <bits/stdc++.h>

using namespace std;

const long long mod = (int)1e9+7;
const int maxn = 3005;
long long fakt[maxn], inv[maxn], lefed[maxn][2], dp[maxn][2];

long long hatvany(long long x, long long h){
    return h ? (h & 1ll ? hatvany(x*x%mod, h>>1)*x%mod : hatvany(x*x%mod, h>>1)) : 1ll;
}

long long komb(int n, int k){
    if(n < 0 || n < k || k < 0) return 0;
    return fakt[n]*(inv[k]*inv[n-k]%mod)%mod;
}

int main(){

    fakt[0] = 1;
    for(int i = 1; i < maxn; i++)
        fakt[i] = fakt[i-1] * i % mod;
    inv[maxn-1] = hatvany(fakt[maxn-1], mod-2);
    for(int i = maxn-2; i >= 0; i--)
        inv[i] = inv[i+1]*(i+1)%mod;

    int n, k;
    cin>>n>>k;

    if(k+1 >= n){
        cout<<fakt[n]<<'\n';
        return 0;
    }

    lefed[n-k][0] = 1;
    for(int i = n-k+1; i <= n; i++){
        for(int j = max(0, i-n+k+1); j < i; j++){
            lefed[i][0] = (lefed[i][0] + lefed[j][1])%mod;
            lefed[i][1] = (lefed[i][1] + lefed[j][0])%mod;
        }
    }

    dp[0][1] = 1;
    for(int i = 1; i <= n; i++){
        dp[i][0] = dp[i-1][0] * i % mod;
        dp[i][1] = dp[i-1][1] * i % mod;
        for(int j = 0; j <= i-n+k; j++){
            long long x = komb(i, i-j);
            dp[i][0] = (dp[i][0] + (dp[j][0] * lefed[i-j][1] %mod) * x + (dp[j][1] * lefed[i-j][0] %mod) * x) % mod;
            dp[i][1] = (dp[i][1] + (dp[j][0] * lefed[i-j][0] %mod) * x + (dp[j][1] * lefed[i-j][1] %mod) * x) % mod;
        }
    }

    cout<<(dp[n][0] - dp[n][1] + fakt[n] + mod)%mod<<'\n';

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
3Accepted4ms316 KiB
subtask212/12
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
subtask311/11
8Accepted34ms316 KiB
9Accepted30ms460 KiB
10Accepted4ms452 KiB
11Accepted34ms316 KiB
subtask423/23
12Accepted1ms316 KiB
13Accepted1ms316 KiB
14Accepted1ms316 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
subtask519/19
17Accepted2ms316 KiB
18Accepted1ms316 KiB
19Accepted1ms316 KiB
20Accepted1ms316 KiB
21Accepted1ms316 KiB
subtask635/35
22Accepted1ms320 KiB
23Accepted1ms508 KiB
24Accepted1ms316 KiB
25Accepted37ms512 KiB
26Accepted65ms508 KiB
27Accepted1ms316 KiB
28Accepted54ms472 KiB
29Accepted1ms316 KiB
30Accepted1ms316 KiB