50432023-04-10 21:32:35Szin AttilaMisztikus táblázatcpp14Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted43ms64568 KiB
2Accepted43ms64876 KiB
3Accepted772ms70844 KiB
subtask20/5
4Time limit exceeded1.042s51420 KiB
5Time limit exceeded1.062s64552 KiB
6Time limit exceeded1.047s77740 KiB
7Time limit exceeded1.067s91040 KiB
subtask30/9
8Accepted37ms123200 KiB
9Accepted37ms123412 KiB
10Time limit exceeded1.059s101048 KiB
11Time limit exceeded1.065s101452 KiB
subtask415/15
12Accepted43ms133564 KiB
13Accepted43ms133256 KiB
14Accepted37ms133564 KiB
15Accepted37ms133864 KiB
16Accepted35ms134288 KiB
17Accepted35ms134352 KiB
18Accepted43ms133940 KiB
19Accepted37ms134204 KiB
subtask50/16
20Accepted35ms133984 KiB
21Accepted35ms134356 KiB
22Time limit exceeded1.088s102312 KiB
23Accepted43ms134836 KiB
24Accepted485ms134824 KiB
subtask625/25
25Accepted52ms134616 KiB
26Accepted50ms134660 KiB
27Accepted54ms134416 KiB
28Accepted46ms134476 KiB
29Accepted50ms134460 KiB
30Accepted52ms134416 KiB
31Accepted52ms134416 KiB
32Accepted52ms134692 KiB
subtask70/30
33Accepted162ms134788 KiB
34Accepted134ms134792 KiB
35Time limit exceeded1.085s102500 KiB
36Accepted428ms134968 KiB
37Time limit exceeded1.024s134948 KiB
38Time limit exceeded1.067s102592 KiB
39Time limit exceeded1.059s102688 KiB
40Accepted873ms135120 KiB
41Time limit exceeded1.06s102820 KiB
42Time limit exceeded1.082s102940 KiB