187512025-11-04 11:18:09algoproPermutációkcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Elfogadva4ms316 KiB
subtask212/12
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
subtask311/11
8Elfogadva34ms316 KiB
9Elfogadva30ms460 KiB
10Elfogadva4ms452 KiB
11Elfogadva34ms316 KiB
subtask423/23
12Elfogadva1ms316 KiB
13Elfogadva1ms316 KiB
14Elfogadva1ms316 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
subtask519/19
17Elfogadva2ms316 KiB
18Elfogadva1ms316 KiB
19Elfogadva1ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
subtask635/35
22Elfogadva1ms320 KiB
23Elfogadva1ms508 KiB
24Elfogadva1ms316 KiB
25Elfogadva37ms512 KiB
26Elfogadva65ms508 KiB
27Elfogadva1ms316 KiB
28Elfogadva54ms472 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB