50442023-04-10 21:36:36Szin AttilaMisztikus táblázatcpp14Accepted 100/100437ms98148 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;
    vector<bool> prev(n+1, 0);
    for(ll i = 0; i < k; i++) {
        vector<bool> cur(n+1, 1);
        for(ll j = 0; j < l; j++) {
            ll x;
            cin >> x;
            cur[x] = 0;
        }

        ll cnt = 0;
        for(int i = 1; i <= n; i++) if(cur[i] + prev[i] == 2) 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
1Accepted46ms64628 KiB
2Accepted45ms64740 KiB
3Accepted159ms65300 KiB
subtask25/5
4Accepted409ms68456 KiB
5Accepted425ms72384 KiB
6Accepted437ms76968 KiB
7Accepted437ms81264 KiB
subtask39/9
8Accepted37ms81304 KiB
9Accepted37ms81708 KiB
10Accepted416ms85488 KiB
11Accepted425ms89580 KiB
subtask415/15
12Accepted43ms89624 KiB
13Accepted43ms89664 KiB
14Accepted37ms89288 KiB
15Accepted35ms89424 KiB
16Accepted35ms89624 KiB
17Accepted43ms89396 KiB
18Accepted43ms89444 KiB
19Accepted43ms89656 KiB
subtask516/16
20Accepted43ms89560 KiB
21Accepted43ms89816 KiB
22Accepted421ms93160 KiB
23Accepted37ms93300 KiB
24Accepted165ms93308 KiB
subtask625/25
25Accepted46ms93308 KiB
26Accepted46ms93224 KiB
27Accepted39ms93260 KiB
28Accepted43ms93252 KiB
29Accepted43ms93472 KiB
30Accepted46ms93472 KiB
31Accepted45ms93472 KiB
32Accepted45ms93436 KiB
subtask730/30
33Accepted76ms93472 KiB
34Accepted68ms93564 KiB
35Accepted435ms97148 KiB
36Accepted50ms97144 KiB
37Accepted150ms97188 KiB
38Accepted293ms97612 KiB
39Accepted229ms97740 KiB
40Accepted67ms97736 KiB
41Accepted180ms98060 KiB
42Accepted307ms98148 KiB