/**
* user: frolov-001
* fname: Konstantin
* lname: Frolov
* task: fishing
* score: 100.0
* date: 2019-10-11 08:36:38.611566
*/
#include <bits/stdc++.h>
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define debug(x) std::cout << #x << ": " << x << '\n';
#define pb push_back
typedef long long ll;
const int N = 200, MOD = 1e9 + 7;
int dp[N][N][N][3][2];
void add(int &x, int y) {
x += y;
if (x >= MOD) x -= MOD;
}
int mult(int a, int b) {
return (a * 1LL * b) % MOD;
}
void reCount(int AB, int BC, int AC, int turn, int has) {
if (dp[AB][BC][AC][turn][has] != -1) return;
dp[AB][BC][AC][turn][has] = 0;
int all = (AB + BC + AC) * 2;
int m[] = {AB, BC, AC};
int other1 = (turn + 1) % 3, other2 = (turn + 2) % 3;
int hasEmptyTurn = (m[other2] != 0);
// debug(AB << ' ' << BC << ' ' << AC << ' ' << turn << ' ' << has)
// debug(hasEmptyTurn)
if (!hasEmptyTurn && m[turn] == 0) {
if (turn == 2) {
if (!has) return;
reCount(m[0], m[1], m[2], 0, 0);
add(dp[AB][BC][AC][turn][has], dp[m[0]][m[1]][m[2]][0][0]);
}
else {
reCount(m[0], m[1], m[2], turn + 1, has);
add(dp[AB][BC][AC][turn][has], dp[m[0]][m[1]][m[2]][turn + 1][has]);
}
}
if (hasEmptyTurn) {
m[other1]++;
m[other2]--;
if (turn == 2 && has) {
reCount(m[0], m[1], m[2], 0, 0);
add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][0][0], m[other2] + 1));
}
else if (turn != 2) {
reCount(m[0], m[1], m[2], turn + 1, has);
// debug
// debug(m[other2] + 1 << ' ' << turn << ' ' << AB << ' ' << BC << ' ' << AC)
add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][turn + 1][has], m[other2] + 1));
}
m[other1]--;
m[other2]++;
}
if (m[turn] != 0) {
m[turn]--;
if (turn == 2) {
reCount(m[0], m[1], m[2], 0, 0);
// reCount(dp[m[0]][m[1]][m[2]][0][0]);
add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][0][0], m[turn] + 1));
// add(dp[m[0]][m[1]][m[2]][(turn + 1) % 3][1], mult(dp[AB][BC][AC][turn][has], (m[turn] + 1)));
}
else {
reCount(m[0], m[1], m[2], turn + 1, 1);
// reCount(dp[m[0]][m[1]][m[2]][turn + 1][1]);
add(dp[AB][BC][AC][turn][has], mult(dp[m[0]][m[1]][m[2]][turn + 1][1], m[turn] + 1));
}
}
}
int inter(std::set<int> &a, std::set<int> &b) {
int cnt = 0;
for (auto e : a) cnt += b.count(e);
return cnt;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);
int t, n;
std::cin >> n >> t;
while (t--) {
memset(dp, -1, sizeof(dp));
std::set<int> A, B, C;
FOR(i, 2 * n) {
int x;
std::cin >> x;
if (A.count(x)) {
A.erase(x);
}
else {
A.insert(x);
}
}
FOR(i, 2 * n) {
int x;
std::cin >> x;
if (B.count(x)) {
B.erase(x);
}
else {
B.insert(x);
}
}
FOR(i, 2 * n) {
int x;
std::cin >> x;
if (C.count(x)) {
C.erase(x);
}
else {
C.insert(x);
}
}
FOR(j, 3) {
FOR(q, 2) {
dp[0][0][0][j][q] = 1;
}
}
reCount(inter(A, B), inter(B, C), inter(A, C), 0, 0);
std::cout << dp[inter(A, B)][inter(B, C)][inter(A, C)][0][0] << '\n';
}
}
Compilation message
fishing.cpp: In function 'void reCount(int, int, int, int, int)':
fishing.cpp:26:6: warning: unused variable 'all' [-Wunused-variable]
int all = (AB + BC + AC) * 2;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
188280 KB |
Output is correct |
| 2 |
Correct |
294 ms |
188268 KB |
Output is correct |
| 3 |
Correct |
290 ms |
188152 KB |
Output is correct |
| 4 |
Correct |
299 ms |
188260 KB |
Output is correct |
| 5 |
Correct |
541 ms |
188300 KB |
Output is correct |
| 6 |
Correct |
604 ms |
188344 KB |
Output is correct |
| 7 |
Correct |
696 ms |
188408 KB |
Output is correct |
| 8 |
Correct |
798 ms |
188508 KB |
Output is correct |
| 9 |
Correct |
936 ms |
188484 KB |
Output is correct |
| 10 |
Correct |
1131 ms |
188380 KB |
Output is correct |
