50422023-04-10 21:25:40Szin AttilaMisztikus táblázatcpp14Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted35ms64836 KiB
2Accepted35ms64860 KiB
3Wrong answer776ms70936 KiB
subtask20/5
4Time limit exceeded1.049s52112 KiB
5Time limit exceeded1.065s65744 KiB
6Time limit exceeded1.062s79432 KiB
7Time limit exceeded1.052s92964 KiB
subtask30/9
8Accepted35ms124792 KiB
9Accepted35ms124792 KiB
10Time limit exceeded1.054s106556 KiB
11Time limit exceeded1.049s120284 KiB
subtask415/15
12Accepted35ms152584 KiB
13Accepted35ms152224 KiB
14Accepted35ms152788 KiB
15Accepted35ms152800 KiB
16Accepted35ms152752 KiB
17Accepted43ms152996 KiB
18Accepted37ms152856 KiB
19Accepted35ms152852 KiB
subtask50/16
20Accepted43ms152860 KiB
21Wrong answer37ms152860 KiB
22Time limit exceeded1.1s131752 KiB
23Wrong answer37ms164112 KiB
24Wrong answer483ms164112 KiB
subtask60/25
25Wrong answer45ms163936 KiB
26Accepted43ms163908 KiB
27Accepted46ms163932 KiB
28Wrong answer39ms163924 KiB
29Wrong answer43ms163872 KiB
30Wrong answer45ms163936 KiB
31Accepted43ms163856 KiB
32Wrong answer45ms163932 KiB
subtask70/30
33Wrong answer152ms164108 KiB
34Accepted125ms164108 KiB
35Time limit exceeded1.075s131736 KiB
36Wrong answer441ms164204 KiB
37Time limit exceeded1.021s131728 KiB
38Time limit exceeded1.07s131796 KiB
39Time limit exceeded1.067s131800 KiB
40Accepted919ms164196 KiB
41Time limit exceeded1.07s131776 KiB
42Time limit exceeded1.083s131740 KiB