5043 | 2023-04-10 21:32:35 | Szin Attila | Misztikus táblázat | cpp14 | Time limit exceeded 40/100 | 1.088s | 135120 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 43ms | 64568 KiB | ||||
2 | Accepted | 43ms | 64876 KiB | ||||
3 | Accepted | 772ms | 70844 KiB | ||||
subtask2 | 0/5 | ||||||
4 | Time limit exceeded | 1.042s | 51420 KiB | ||||
5 | Time limit exceeded | 1.062s | 64552 KiB | ||||
6 | Time limit exceeded | 1.047s | 77740 KiB | ||||
7 | Time limit exceeded | 1.067s | 91040 KiB | ||||
subtask3 | 0/9 | ||||||
8 | Accepted | 37ms | 123200 KiB | ||||
9 | Accepted | 37ms | 123412 KiB | ||||
10 | Time limit exceeded | 1.059s | 101048 KiB | ||||
11 | Time limit exceeded | 1.065s | 101452 KiB | ||||
subtask4 | 15/15 | ||||||
12 | Accepted | 43ms | 133564 KiB | ||||
13 | Accepted | 43ms | 133256 KiB | ||||
14 | Accepted | 37ms | 133564 KiB | ||||
15 | Accepted | 37ms | 133864 KiB | ||||
16 | Accepted | 35ms | 134288 KiB | ||||
17 | Accepted | 35ms | 134352 KiB | ||||
18 | Accepted | 43ms | 133940 KiB | ||||
19 | Accepted | 37ms | 134204 KiB | ||||
subtask5 | 0/16 | ||||||
20 | Accepted | 35ms | 133984 KiB | ||||
21 | Accepted | 35ms | 134356 KiB | ||||
22 | Time limit exceeded | 1.088s | 102312 KiB | ||||
23 | Accepted | 43ms | 134836 KiB | ||||
24 | Accepted | 485ms | 134824 KiB | ||||
subtask6 | 25/25 | ||||||
25 | Accepted | 52ms | 134616 KiB | ||||
26 | Accepted | 50ms | 134660 KiB | ||||
27 | Accepted | 54ms | 134416 KiB | ||||
28 | Accepted | 46ms | 134476 KiB | ||||
29 | Accepted | 50ms | 134460 KiB | ||||
30 | Accepted | 52ms | 134416 KiB | ||||
31 | Accepted | 52ms | 134416 KiB | ||||
32 | Accepted | 52ms | 134692 KiB | ||||
subtask7 | 0/30 | ||||||
33 | Accepted | 162ms | 134788 KiB | ||||
34 | Accepted | 134ms | 134792 KiB | ||||
35 | Time limit exceeded | 1.085s | 102500 KiB | ||||
36 | Accepted | 428ms | 134968 KiB | ||||
37 | Time limit exceeded | 1.024s | 134948 KiB | ||||
38 | Time limit exceeded | 1.067s | 102592 KiB | ||||
39 | Time limit exceeded | 1.059s | 102688 KiB | ||||
40 | Accepted | 873ms | 135120 KiB | ||||
41 | Time limit exceeded | 1.06s | 102820 KiB | ||||
42 | Time limit exceeded | 1.082s | 102940 KiB |