#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,sse4,bmi,bmi2,fma,popcnt,lzcnt")
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//template <class K, class V>
// using ht =
// gp_hash_table<K, V, hash<K>, equal_to<K>, direct_mask_range_hashing<>,
// linear_probe_fn<>,
// hash_standard_resize_policy<hash_exponential_size_policy<>,
// hash_load_check_resize_trigger<>, true>>;
using ll = long long; using pii = pair<ll,ll>;
ll N;
const ll p = 1e9+7;
const int pc1 = 255;
unordered_map<int,ll> dp;
array<int,3> garr(int x) {
return (array<int,3>{x>>16,(x>>8)&pc1,x&pc1});
}
int gv(array<int,3> a0) {
return ((a0[0]<<16LL)+(a0[1]<<8LL)+a0[2]);
}
ll g1Y(int a, int b, int c) { //Y = round already cleared
if ((a<0)||(b<0)||(c<0)) return 0;
if ((a+b)==0) {
return dp[gv({a,b,c})];
}
ll v = 0;
//if (b>=0) {
v+= b*dp[gv({a,b-1,c})];
//}
//if (a>=0) {
v+= a*dp[gv({a-1,b,c+1})];
//}
return (v%p);
}
ll g1N(int a, int b, int c) { //N = round not cleared yet
if ((a<0)||(b<0)||(c<0)) return 0;
return (b*dp[gv({a,b-1,c})])%p;
}
ll g2Y(int a, int b, int c) {
if ((a<0)||(b<0)||(c<0)) return 0;
if ((a+c)==0) {
return g1Y(a,b,c);
}
ll v = 0;
v += a*g1Y(a-1,b,c);
v += c*g1Y(a,b+1,c-1);
return (v%p);
}
ll g2N(int a, int b, int c) {
if ((a<0)||(b<0)||(c<0)) return 0;
//cout << "calling g2N at a,b,c="<<a<<","<<b<<","<<c<<"\n";
if ((a+c)==0) {
return g1N(a,b,c);
}
ll v = 0;
v += a*g1Y(a-1,b,c);
v += c*g1N(a,b+1,c-1);
return (v%p);
}
ll gdp(int a, int b, int c) {
if ((a<0)||(b<0)||(c<0)) return 0;
if ((b+c)==0) {
return g2N(a,b,c);
}
ll v = 0;
v += c*g2Y(a,b,c-1);
v += b*g2N(a+1,b-1,c);
//cout << "gdp at a,b,c="<<a<<","<<b<<","<<c<<"="<<v<<"\n";
return (v%p);
}
void solve() {
dp.clear();
vector<ll> va,vb,vc;
int prt[3*N];
for (ll i=0;i<(3*N);i++) {
prt[i]=0;
}
for (int i=0;i<(2*N);i++) {
int x; cin >> x; x--; //A
prt[x]^=1;
}
for (int i=0;i<(2*N);i++) {
int x; cin >> x; x--; //B
prt[x]^=2;
}
for (int i=0;i<(2*N);i++) {
int x; cin >> x; x--; //C
prt[x]^=4;
}
int nea=0,neb=0,nec=0;
for (int i=0;i<(3*N);i++) {
if (prt[i]==3) {
nec++;
}
if (prt[i]==5) {
neb++;
}
if (prt[i]==6) {
nea++;
}
}
ll SM = nea+neb+nec;
//cout << "nea,neb,nec="<<nea<<","<<neb<<","<<nec<<"\n";
dp[0]=1;
for (int S=1;S<=SM;S++) {
for (int a=0;a<=S;a++) {
for (int b=0;b<=(S-a);b++) {
int c = S-a-b;
dp[gv({a,b,c})]=gdp(a,b,c);
}
}
}
cout << dp[gv({nea,neb,nec})] <<"\n";
}
int main() {
dp.reserve(1LL<<25);
ll T;
cin >> N >> T;
while(T--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
264272 KB |
Output is correct |
| 2 |
Correct |
62 ms |
264144 KB |
Output is correct |
| 3 |
Correct |
65 ms |
264520 KB |
Output is correct |
| 4 |
Correct |
69 ms |
265432 KB |
Output is correct |
| 5 |
Correct |
279 ms |
283208 KB |
Output is correct |
| 6 |
Correct |
444 ms |
296652 KB |
Output is correct |
| 7 |
Correct |
677 ms |
315208 KB |
Output is correct |
| 8 |
Correct |
918 ms |
339940 KB |
Output is correct |
| 9 |
Correct |
1178 ms |
371528 KB |
Output is correct |
| 10 |
Correct |
1685 ms |
405508 KB |
Output is correct |
