50442023-04-10 21:36:36Szin AttilaMisztikus táblázatcpp14Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva46ms64628 KiB
2Elfogadva45ms64740 KiB
3Elfogadva159ms65300 KiB
subtask25/5
4Elfogadva409ms68456 KiB
5Elfogadva425ms72384 KiB
6Elfogadva437ms76968 KiB
7Elfogadva437ms81264 KiB
subtask39/9
8Elfogadva37ms81304 KiB
9Elfogadva37ms81708 KiB
10Elfogadva416ms85488 KiB
11Elfogadva425ms89580 KiB
subtask415/15
12Elfogadva43ms89624 KiB
13Elfogadva43ms89664 KiB
14Elfogadva37ms89288 KiB
15Elfogadva35ms89424 KiB
16Elfogadva35ms89624 KiB
17Elfogadva43ms89396 KiB
18Elfogadva43ms89444 KiB
19Elfogadva43ms89656 KiB
subtask516/16
20Elfogadva43ms89560 KiB
21Elfogadva43ms89816 KiB
22Elfogadva421ms93160 KiB
23Elfogadva37ms93300 KiB
24Elfogadva165ms93308 KiB
subtask625/25
25Elfogadva46ms93308 KiB
26Elfogadva46ms93224 KiB
27Elfogadva39ms93260 KiB
28Elfogadva43ms93252 KiB
29Elfogadva43ms93472 KiB
30Elfogadva46ms93472 KiB
31Elfogadva45ms93472 KiB
32Elfogadva45ms93436 KiB
subtask730/30
33Elfogadva76ms93472 KiB
34Elfogadva68ms93564 KiB
35Elfogadva435ms97148 KiB
36Elfogadva50ms97144 KiB
37Elfogadva150ms97188 KiB
38Elfogadva293ms97612 KiB
39Elfogadva229ms97740 KiB
40Elfogadva67ms97736 KiB
41Elfogadva180ms98060 KiB
42Elfogadva307ms98148 KiB