50432023-04-10 21:32:35Szin AttilaMisztikus táblázatcpp14Időlimit túllépés 40/1001.088s135120 KiB
#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const ll maxN = 2e3 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 7;

ll power(ll a, ll b) {
    ll res = 1;
    while(b > 0) {
        if(b % 2) res = (res * a) % MOD;
        a = (a*a) % MOD;
        b /= 2;
    }
    return res;
}


int main() {
   InTheNameOfGod;

    vector<vector<ll> > dp(maxN, vector<ll>(maxN, 0));
    dp[0][0] = 1;
    for(ll i = 1; i < maxN; i++) {
        dp[i][0] = (dp[i-1][0] * i) % MOD;
        dp[i][1] = (dp[i-1][0] * (i-1)) % MOD;
    }

    for(ll j = 2; j  < maxN; j++) {
        for(ll i = j; i < maxN; i++) {
            dp[i][j] = ((j-1)*dp[i-1][j-2] + (i-j)*dp[i-1][j-1]) % MOD;
        }
    }

    ll n,k,l;
    cin >> n >> k >> l;

    ll mo = 1;
    set<ll> prev;
    for(ll i = 0; i < k; i++) {
        set<ll> cur;
        for(ll j = 1; j <= n; j++) cur.insert(j);
        for(ll j = 0; j < l; j++) {
            ll x;
            cin >> x;
            cur.erase(x);
        }

        ll cnt = 0;
        for(ll j : cur) if(prev.find(j) != prev.end()) cnt++;
        mo *= dp[n-l][cnt];
        mo %= MOD;
        prev = cur;
    }

    mo *= power(dp[n][n], n-k);
    mo %= MOD;
    cout << mo;

    
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva43ms64568 KiB
2Elfogadva43ms64876 KiB
3Elfogadva772ms70844 KiB
subtask20/5
4Időlimit túllépés1.042s51420 KiB
5Időlimit túllépés1.062s64552 KiB
6Időlimit túllépés1.047s77740 KiB
7Időlimit túllépés1.067s91040 KiB
subtask30/9
8Elfogadva37ms123200 KiB
9Elfogadva37ms123412 KiB
10Időlimit túllépés1.059s101048 KiB
11Időlimit túllépés1.065s101452 KiB
subtask415/15
12Elfogadva43ms133564 KiB
13Elfogadva43ms133256 KiB
14Elfogadva37ms133564 KiB
15Elfogadva37ms133864 KiB
16Elfogadva35ms134288 KiB
17Elfogadva35ms134352 KiB
18Elfogadva43ms133940 KiB
19Elfogadva37ms134204 KiB
subtask50/16
20Elfogadva35ms133984 KiB
21Elfogadva35ms134356 KiB
22Időlimit túllépés1.088s102312 KiB
23Elfogadva43ms134836 KiB
24Elfogadva485ms134824 KiB
subtask625/25
25Elfogadva52ms134616 KiB
26Elfogadva50ms134660 KiB
27Elfogadva54ms134416 KiB
28Elfogadva46ms134476 KiB
29Elfogadva50ms134460 KiB
30Elfogadva52ms134416 KiB
31Elfogadva52ms134416 KiB
32Elfogadva52ms134692 KiB
subtask70/30
33Elfogadva162ms134788 KiB
34Elfogadva134ms134792 KiB
35Időlimit túllépés1.085s102500 KiB
36Elfogadva428ms134968 KiB
37Időlimit túllépés1.024s134948 KiB
38Időlimit túllépés1.067s102592 KiB
39Időlimit túllépés1.059s102688 KiB
40Elfogadva873ms135120 KiB
41Időlimit túllépés1.06s102820 KiB
42Időlimit túllépés1.082s102940 KiB