| 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 | ||||