/**
* user: puzic-97a
* fname: Mladen
* lname: Puzic
* task: fishing
* score: 100.0
* date: 2019-10-11 07:39:11.906428
*/
#include <bits/stdc++.h>
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define NL(x) " \n"[(x)]
#define sz(x) int((x).size())
#define all(x) begin(x),end(x)
#define mid (l+r)/2
#define fi first
#define se second
#define pb push_back
#define endl '\n'
#define lld long long
#define pii pair<int,int>
#define pli pair<lld,int>
#define pil pair<int,lld>
#define pll pair<lld,lld>
#define INF 1000000000
#define LINF 1000000000000000000LL
#define EPS 1e-9
using namespace std;
#define MOD 1000000007
#define MAXN 210
lld dp[MAXN][MAXN][MAXN][3][2];
int N, T;
set<int> A, B, C;
lld bt(lld AB, lld BC, lld CA, int k, int t) {
/*PRINT(AB);
PRINT(BC);
PRINT(CA);
PRINT(k);
PRINT(t);*/
if(dp[AB][BC][CA][k][t] != -1) return dp[AB][BC][CA][k][t];
dp[AB][BC][CA][k][t] = 0;
if(k == 0) {
if(AB > 0) dp[AB][BC][CA][k][t] += AB*bt(AB-1, BC, CA, 1, 1);
if(CA > 0) dp[AB][BC][CA][k][t] += CA*bt(AB, BC+1, CA-1, 1, t);
if(AB == 0 && CA == 0) dp[AB][BC][CA][k][t] += bt(AB, BC, CA, 1, t);
} else if(k == 1) {
if(BC > 0) dp[AB][BC][CA][k][t] += BC*bt(AB, BC-1, CA, 2, 1);
if(AB > 0) dp[AB][BC][CA][k][t] += AB*bt(AB-1, BC, CA+1, 2, t);
if(BC == 0 && AB == 0) dp[AB][BC][CA][k][t] += bt(AB, BC, CA, 2, t);
} else if(k == 2) {
if(t == 0 && CA == 0) return 0;
if(CA > 0) dp[AB][BC][CA][k][t] += CA*bt(AB, BC, CA-1, 0, 0);
if(t == 1 && BC > 0) dp[AB][BC][CA][k][t] += BC*bt(AB+1, BC-1, CA, 0, 0);
if(CA == 0 && BC == 0) dp[AB][BC][CA][k][t] += bt(AB, BC, CA, 0, 0);
}
if(dp[AB][BC][CA][k][t] >= MOD) dp[AB][BC][CA][k][t] %= MOD;
return dp[AB][BC][CA][k][t];
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
for(int i = 0; i < MAXN; i++) {
for(int j = 0; j < MAXN; j++) {
for(int k = 0; k < MAXN; k++) dp[i][j][k][0][0] = dp[i][j][k][1][0] = dp[i][j][k][2][0] = dp[i][j][k][0][1] = dp[i][j][k][1][1] = dp[i][j][k][2][1] = -1;
}
}
dp[0][0][0][0][0] = 1;
cin >> N >> T;
while(T--) {
A.clear(); B.clear(); C.clear();
lld AB = 0, BC = 0, CA = 0;
for(int i = 0; i < 2*N; i++) {
int x; cin >> x;
if(A.find(x) != A.end()) A.erase(x);
else A.insert(x);
}
for(int i = 0; i < 2*N; i++) {
int x; cin >> x;
if(B.find(x) != B.end()) B.erase(x);
else B.insert(x);
}
for(int i = 0; i < 2*N; i++) {
int x; cin >> x;
if(C.find(x) != C.end()) C.erase(x);
else C.insert(x);
}
for(auto x : A) {
if(B.find(x) != B.end()) AB++;
if(C.find(x) != C.end()) CA++;
}
for(auto x : B) {
if(C.find(x) != C.end()) BC++;
}
cout << bt(AB, BC, CA, 0, 0) << endl;
}
return 0;
}
/*
1 5
1 2
2 3
3 1
1 1
2 3
3 2
1 1
2 2
3 3
1 3
2 2
3 1
1 2
2 1
3 3
1 1
1 1
2 3
3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
273 ms |
435308 KB |
Output is correct |
| 2 |
Correct |
254 ms |
435328 KB |
Output is correct |
| 3 |
Correct |
247 ms |
435308 KB |
Output is correct |
| 4 |
Correct |
242 ms |
435436 KB |
Output is correct |
| 5 |
Correct |
278 ms |
435308 KB |
Output is correct |
| 6 |
Correct |
283 ms |
435308 KB |
Output is correct |
| 7 |
Correct |
282 ms |
435308 KB |
Output is correct |
| 8 |
Correct |
330 ms |
435420 KB |
Output is correct |
| 9 |
Correct |
338 ms |
435308 KB |
Output is correct |
| 10 |
Correct |
387 ms |
435308 KB |
Output is correct |
