#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int kN = 100;
int n, dp[2 * kN][2 * kN][2 * kN];
bitset<3 * kN> a[3];
/// dp[i][j][k] =def= numarul de modalitati distincte de desfasurare ale jocului astfel inca A si B
/// au in comun la inceput i carti, B si C au j carti, iar C si A au k carti
/// Se observa ca 2 * (i + j + k) este numarul total de carti de pe masa(duplicatele pe care le
/// detine oricine la inceput trebuie eliminate). De asemenea, la fiecare runda a jocului
/// aceasta cantitate va trebui redusa si va fi redusa cu un numar de 2 * p carti(o pereche este
/// eliminata "impreuna").
/// Sa fixam toate tipurile de interactiuni ce pot avea loc intre A si B intr-o runda. Celelalte 2
/// cazuri vor fi simetrice:
/// (1) A nu are ce carte sa ii dea lui B. In acest caz, i + k = 0(A si B, respectiv A si C nu pot
/// avea carti comune daca A nu are carti deloc).
/// (2) A ii da lui B o carte pe care o au cei 2 in comun. => i variante de a face asta, iar i scade
/// in urma acestei operatii pentru ca A nu mai detine cartea oferita.
/// (3) A ii da lui B o carte pe care o are in comun cu C. => k variante de a face asta, iar j creste
/// si k scade dupa aceasta operatie(C si A au o carte in minus in comun, iar B si C una in plus).
/// Se observa ca suma ramane constanta dupa o operatie de tipul (1) sau (3), deci orice runda trebuie
/// sa contina cel putin o operatie de tipul 2 pentru a satisface conditia din enunt.
void addSelf(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
int mult(int x, int y) {
return (int64_t)x * y % mod;
}
void apply1(int &ways, int i, int j, int k) {
if (i + k != 0) {
ways = 0;
}
}
void apply2(int &ways, int &i, int j, int k) {
ways *= i;
i -= 1;
}
void apply3(int &ways, int i, int &j, int &k) {
ways *= k;
j += 1;
k -= 1;
}
void precalc() {
dp[0][0][0] = 1;
for (int total = 1; total <= 6 * n; ++total) {
for (int i = 0; i <= 2 * n && i <= total; ++i) {
for (int j = 0; j <= 2 * n && i + j <= total && i + j <= 3 * n; ++j) {
int k = total - i - j;
if (i + k > 3 * n || j + k > 3 * n) {
continue;
}
for (int ab = 1; ab <= 3; ++ab) {
for (int bc = 1; bc <= 3; ++bc) {
for (int ca = 1; ca <= 3; ++ca) {
if (ab != 2 && bc != 2 && ca != 2) {
continue;
}
int ways = 1, newI = i, newJ = j, newK = k;
if (ab == 1) {
apply1(ways, newI, newJ, newK);
} else if (ab == 2) {
apply2(ways, newI, newJ, newK);
} else {
apply3(ways, newI, newJ, newK);
}
if (ways == 0 || newI < 0 || newJ < 0 || newK < 0) {
continue;
}
if (bc == 1) {
apply1(ways, newJ, newK, newI);
} else if (bc == 2) {
apply2(ways, newJ, newK, newI);
} else {
apply3(ways, newJ, newK, newI);
}
if (ways == 0 || newI < 0 || newJ < 0 || newK < 0) {
continue;
}
if (ca == 1) {
apply1(ways, newK, newI, newJ);
} else if (ca == 2) {
apply2(ways, newK, newI, newJ);
} else {
apply3(ways, newK, newI, newJ);
}
if (ways == 0 || newI < 0 || newJ < 0 || newK < 0) {
continue;
}
addSelf(dp[i][j][k], mult(ways, dp[newI][newJ][newK]));
}
}
}
}
}
}
}
void testCase() {
for (int i = 0; i < 3; ++i) {
a[i].reset();
for (int j = 0; j < 2 * n; ++j) {
int x;
cin >> x;
a[i][x] = true;
}
}
int ab = (a[0] & a[1]).count(), bc = (a[1] & a[2]).count(), ca = (a[2] & a[0]).count();
cout << dp[ab][bc][ca] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests;
cin >> n >> tests;
precalc();
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1572 KB |
Output is correct |
| 5 |
Correct |
99 ms |
7632 KB |
Output is correct |
| 6 |
Correct |
132 ms |
10748 KB |
Output is correct |
| 7 |
Correct |
233 ms |
14408 KB |
Output is correct |
| 8 |
Correct |
343 ms |
18580 KB |
Output is correct |
| 9 |
Correct |
442 ms |
23416 KB |
Output is correct |
| 10 |
Correct |
641 ms |
27868 KB |
Output is correct |
