5044 | 2023-04-10 21:36:36 | Szin Attila | Misztikus táblázat | cpp14 | Elfogadva 100/100 | 437ms | 98148 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 46ms | 64628 KiB | ||||
2 | Elfogadva | 45ms | 64740 KiB | ||||
3 | Elfogadva | 159ms | 65300 KiB | ||||
subtask2 | 5/5 | ||||||
4 | Elfogadva | 409ms | 68456 KiB | ||||
5 | Elfogadva | 425ms | 72384 KiB | ||||
6 | Elfogadva | 437ms | 76968 KiB | ||||
7 | Elfogadva | 437ms | 81264 KiB | ||||
subtask3 | 9/9 | ||||||
8 | Elfogadva | 37ms | 81304 KiB | ||||
9 | Elfogadva | 37ms | 81708 KiB | ||||
10 | Elfogadva | 416ms | 85488 KiB | ||||
11 | Elfogadva | 425ms | 89580 KiB | ||||
subtask4 | 15/15 | ||||||
12 | Elfogadva | 43ms | 89624 KiB | ||||
13 | Elfogadva | 43ms | 89664 KiB | ||||
14 | Elfogadva | 37ms | 89288 KiB | ||||
15 | Elfogadva | 35ms | 89424 KiB | ||||
16 | Elfogadva | 35ms | 89624 KiB | ||||
17 | Elfogadva | 43ms | 89396 KiB | ||||
18 | Elfogadva | 43ms | 89444 KiB | ||||
19 | Elfogadva | 43ms | 89656 KiB | ||||
subtask5 | 16/16 | ||||||
20 | Elfogadva | 43ms | 89560 KiB | ||||
21 | Elfogadva | 43ms | 89816 KiB | ||||
22 | Elfogadva | 421ms | 93160 KiB | ||||
23 | Elfogadva | 37ms | 93300 KiB | ||||
24 | Elfogadva | 165ms | 93308 KiB | ||||
subtask6 | 25/25 | ||||||
25 | Elfogadva | 46ms | 93308 KiB | ||||
26 | Elfogadva | 46ms | 93224 KiB | ||||
27 | Elfogadva | 39ms | 93260 KiB | ||||
28 | Elfogadva | 43ms | 93252 KiB | ||||
29 | Elfogadva | 43ms | 93472 KiB | ||||
30 | Elfogadva | 46ms | 93472 KiB | ||||
31 | Elfogadva | 45ms | 93472 KiB | ||||
32 | Elfogadva | 45ms | 93436 KiB | ||||
subtask7 | 30/30 | ||||||
33 | Elfogadva | 76ms | 93472 KiB | ||||
34 | Elfogadva | 68ms | 93564 KiB | ||||
35 | Elfogadva | 435ms | 97148 KiB | ||||
36 | Elfogadva | 50ms | 97144 KiB | ||||
37 | Elfogadva | 150ms | 97188 KiB | ||||
38 | Elfogadva | 293ms | 97612 KiB | ||||
39 | Elfogadva | 229ms | 97740 KiB | ||||
40 | Elfogadva | 67ms | 97736 KiB | ||||
41 | Elfogadva | 180ms | 98060 KiB | ||||
42 | Elfogadva | 307ms | 98148 KiB |