50422023-04-10 21:25:40Szin AttilaMisztikus táblázatcpp14Hibás válasz 15/1001.1s164204 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 int INF = 1e9 + 7;

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


int main() {

#ifndef ONLINE_JUDGE
   freopen("../input.txt", "r", stdin);
   freopen("../output.txt", "w", stdout);
#endif
   InTheNameOfGod;

    vector<vector<ll> > dp(maxN, vector<ll>(maxN, 0));
    dp[0][0] = 1;
    for(int 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;
        }
    }

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

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

        int cnt = 0;
        for(int 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
1Elfogadva35ms64836 KiB
2Elfogadva35ms64860 KiB
3Hibás válasz776ms70936 KiB
subtask20/5
4Időlimit túllépés1.049s52112 KiB
5Időlimit túllépés1.065s65744 KiB
6Időlimit túllépés1.062s79432 KiB
7Időlimit túllépés1.052s92964 KiB
subtask30/9
8Elfogadva35ms124792 KiB
9Elfogadva35ms124792 KiB
10Időlimit túllépés1.054s106556 KiB
11Időlimit túllépés1.049s120284 KiB
subtask415/15
12Elfogadva35ms152584 KiB
13Elfogadva35ms152224 KiB
14Elfogadva35ms152788 KiB
15Elfogadva35ms152800 KiB
16Elfogadva35ms152752 KiB
17Elfogadva43ms152996 KiB
18Elfogadva37ms152856 KiB
19Elfogadva35ms152852 KiB
subtask50/16
20Elfogadva43ms152860 KiB
21Hibás válasz37ms152860 KiB
22Időlimit túllépés1.1s131752 KiB
23Hibás válasz37ms164112 KiB
24Hibás válasz483ms164112 KiB
subtask60/25
25Hibás válasz45ms163936 KiB
26Elfogadva43ms163908 KiB
27Elfogadva46ms163932 KiB
28Hibás válasz39ms163924 KiB
29Hibás válasz43ms163872 KiB
30Hibás válasz45ms163936 KiB
31Elfogadva43ms163856 KiB
32Hibás válasz45ms163932 KiB
subtask70/30
33Hibás válasz152ms164108 KiB
34Elfogadva125ms164108 KiB
35Időlimit túllépés1.075s131736 KiB
36Hibás válasz441ms164204 KiB
37Időlimit túllépés1.021s131728 KiB
38Időlimit túllépés1.07s131796 KiB
39Időlimit túllépés1.067s131800 KiB
40Elfogadva919ms164196 KiB
41Időlimit túllépés1.07s131776 KiB
42Időlimit túllépés1.083s131740 KiB