187502025-11-04 11:13:54algoproPermutációkcpp17Futási hiba 54/100381ms210920 KiB
// UUID: a21ba884-b261-4171-bb3e-f29e59246440
#include <bits/stdc++.h>

using namespace std;
const int c=305;
long long n, k, fakt[c], dp[c][c][c], ans, mod=1e9+7;

int main()
{
    cin >> n >> k;
    fakt[0]=1;
    for (int i=1; i<=n; i++) {
        fakt[i]=fakt[i-1]*i%mod;
    }
    if (k>=n-1) {
        cout << fakt[n] << "\n";
        return 0;
    }
    k=n-k;


    dp[1][1][0]=1, dp[1][1][n]=mod-1;
    for (int pos=1; pos<=n; pos++) {
        for (int len=1; len<=k; len++) {
            for (int ut=0; ut<=n-pos; ut++) {
                if (ut) dp[pos][len][ut]+=dp[pos][len][ut-1];
                long long ert=dp[pos][len][ut]%mod;

                if (len==k) {
                    ans=(ans+ert*fakt[n-pos])%mod;
                    continue;
                }
                int nagy=n-pos-ut;

                dp[pos+1][1][0]+=ert;
                dp[pos+1][1][ut]+=mod-ert;

                dp[pos+1][len+1][ut]+=ert;
                dp[pos+1][len+1][ut+nagy]+=mod-ert;

            }
        }
    }

    cout << ans << "\n";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
3Futási hiba1ms416 KiB
subtask212/12
4Elfogadva1ms508 KiB
5Elfogadva2ms564 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms320 KiB
subtask30/11
8Futási hiba1ms316 KiB
9Futási hiba1ms316 KiB
10Futási hiba1ms568 KiB
11Futási hiba1ms316 KiB
subtask423/23
12Elfogadva3ms2548 KiB
13Elfogadva14ms12272 KiB
14Elfogadva14ms13108 KiB
15Elfogadva27ms21812 KiB
16Elfogadva1ms408 KiB
subtask519/19
17Elfogadva65ms39732 KiB
18Elfogadva208ms124468 KiB
19Elfogadva381ms210920 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
subtask60/35
22Futási hiba2ms564 KiB
23Futási hiba1ms316 KiB
24Futási hiba2ms564 KiB
25Futási hiba1ms580 KiB
26Futási hiba1ms316 KiB
27Futási hiba1ms316 KiB
28Futási hiba1ms316 KiB
29Futási hiba1ms316 KiB
30Elfogadva1ms316 KiB