5042 | 2023-04-10 21:25:40 | Szin Attila | Misztikus táblázat | cpp14 | Hibás válasz 15/100 | 1.1s | 164204 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 35ms | 64836 KiB | ||||
2 | Elfogadva | 35ms | 64860 KiB | ||||
3 | Hibás válasz | 776ms | 70936 KiB | ||||
subtask2 | 0/5 | ||||||
4 | Időlimit túllépés | 1.049s | 52112 KiB | ||||
5 | Időlimit túllépés | 1.065s | 65744 KiB | ||||
6 | Időlimit túllépés | 1.062s | 79432 KiB | ||||
7 | Időlimit túllépés | 1.052s | 92964 KiB | ||||
subtask3 | 0/9 | ||||||
8 | Elfogadva | 35ms | 124792 KiB | ||||
9 | Elfogadva | 35ms | 124792 KiB | ||||
10 | Időlimit túllépés | 1.054s | 106556 KiB | ||||
11 | Időlimit túllépés | 1.049s | 120284 KiB | ||||
subtask4 | 15/15 | ||||||
12 | Elfogadva | 35ms | 152584 KiB | ||||
13 | Elfogadva | 35ms | 152224 KiB | ||||
14 | Elfogadva | 35ms | 152788 KiB | ||||
15 | Elfogadva | 35ms | 152800 KiB | ||||
16 | Elfogadva | 35ms | 152752 KiB | ||||
17 | Elfogadva | 43ms | 152996 KiB | ||||
18 | Elfogadva | 37ms | 152856 KiB | ||||
19 | Elfogadva | 35ms | 152852 KiB | ||||
subtask5 | 0/16 | ||||||
20 | Elfogadva | 43ms | 152860 KiB | ||||
21 | Hibás válasz | 37ms | 152860 KiB | ||||
22 | Időlimit túllépés | 1.1s | 131752 KiB | ||||
23 | Hibás válasz | 37ms | 164112 KiB | ||||
24 | Hibás válasz | 483ms | 164112 KiB | ||||
subtask6 | 0/25 | ||||||
25 | Hibás válasz | 45ms | 163936 KiB | ||||
26 | Elfogadva | 43ms | 163908 KiB | ||||
27 | Elfogadva | 46ms | 163932 KiB | ||||
28 | Hibás válasz | 39ms | 163924 KiB | ||||
29 | Hibás válasz | 43ms | 163872 KiB | ||||
30 | Hibás válasz | 45ms | 163936 KiB | ||||
31 | Elfogadva | 43ms | 163856 KiB | ||||
32 | Hibás válasz | 45ms | 163932 KiB | ||||
subtask7 | 0/30 | ||||||
33 | Hibás válasz | 152ms | 164108 KiB | ||||
34 | Elfogadva | 125ms | 164108 KiB | ||||
35 | Időlimit túllépés | 1.075s | 131736 KiB | ||||
36 | Hibás válasz | 441ms | 164204 KiB | ||||
37 | Időlimit túllépés | 1.021s | 131728 KiB | ||||
38 | Időlimit túllépés | 1.07s | 131796 KiB | ||||
39 | Időlimit túllépés | 1.067s | 131800 KiB | ||||
40 | Elfogadva | 919ms | 164196 KiB | ||||
41 | Időlimit túllépés | 1.07s | 131776 KiB | ||||
42 | Időlimit túllépés | 1.083s | 131740 KiB |