#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) (ll)(x).size()
#define F first
#define S second
#define pb push_back
#define char unsigned char
#define int long long
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1e9 + 7;
const int MAXN = 3e5 + 4;
const int INF = 2e9;
// -2 -2 0
//
int n;
int dp[301][301][301];
int ab = 0, bc = 0, ca = 0;
inline bool check(int x1, int x2, int x3)
{
if (ab + x1 > 300 || ab + x1 < 0)
return 0;
if (bc + x2 > 300 || bc + x2 < 0)
return 0;
if (ca + x3 > 300 || ca + x3 < 0)
return 0;
return 1;
}
inline void add(int x1, int x2, int x3, int mtp)
{
dp[ab + x1][bc + x2][ca + x3] += dp[ab][bc][ca] * mtp;
dp[ab + x1][bc + x2][ca + x3] %= mod;
}
inline void genshin_impact()
{
array<vector<int>, 3> c;
for (int d = 0; d < 3; d++) {
c[d].resize(2 * n);
for (int i = 0; i < 2 * n; i++)
cin >> c[d][i];
}
for (int i = 1; i <= 3 * n; i++) {
if (find(all(c[0]), i) != c[0].end() && find(all(c[1]), i) != c[1].end())
ab++;
else if (find(all(c[0]), i) != c[0].end() && find(all(c[2]), i) != c[2].end())
ca++;
else if (find(all(c[1]), i) != c[1].end() && find(all(c[2]), i) != c[2].end())
bc++;
}
//cout << ab << ' ' << bc << ' ' << ca << endl;
dp[ab][bc][ca] = 1;
int sum = ab + bc + ca;
for (int s = sum; s >= 1; s--) {
for (ab = 0; ab <= s; ab++) {
for (bc = 0; bc <= s - ab; bc++) {
ca = s - ab - bc;
//cout << ab << ' ' << bc << ' ' << ca << endl;
if (ca + ab == 0) {
if (bc == 1)
add(0, -1, 0, 1);
else if (bc >= 2) {
add(1, -2, 0, bc * (bc - 1));
}
}
else if (ab + bc == 0) {
if (ca == 1)
add(0, 0, -1, 1);
else if (ca >= 2) {
add(0, 0, -2, ca * (ca - 1));
}
}
else if (bc + ca == 0) {
if (ab == 1)
add(-1, 0, 0, 1);
else if (ab >= 2) {
add(-2, 0, 0, ab * (ab - 1));
}
}
else {
if (check(-1, 1, -1)) // 001
add(-1, 1, -1, ab * ca * ca);
if (check(1, -1, -1) && check(0, 1, -1)) // 010
add(1, -1, -1, (bc + 1) * ca * bc);
if (check(-2, -1, 1)) // 100
add(-1, -1, 1, ab * bc * (ab - 1));
if (check(0, 1, -2)) // 011
add(0, 0, -2, ca * (bc + 1) * (ca - 1));
if (check(-2, 0, 1)) // 101
add(-2, 0, 0, ab * (ab - 1) * (ca + 1));
if (check(-1, -2, 0))
add(0, -2, 0, ab * bc * (bc - 1));
if (check(-1, -1, -1))
add(-1, -1, -1, ab * bc * ca);
}
}
}
}
cout << dp[0][0][0] << '\n';
}
/*
1 1
1 2
2 3
1 3
*/
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
int T = 1;
cin >> T;
while(T--) genshin_impact();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
1620 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
5204 KB |
Output isn't correct |
| 5 |
Incorrect |
73 ms |
28456 KB |
Output isn't correct |
| 6 |
Incorrect |
104 ms |
40396 KB |
Output isn't correct |
| 7 |
Incorrect |
187 ms |
54568 KB |
Output isn't correct |
| 8 |
Incorrect |
255 ms |
70784 KB |
Output isn't correct |
| 9 |
Incorrect |
335 ms |
89048 KB |
Output isn't correct |
| 10 |
Incorrect |
471 ms |
107340 KB |
Output isn't correct |
