#include "bits/stdc++.h"
using namespace std;
#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x,v) memset(x,v,sizeof(x))
#define siz(x) ll(x.size())
#define all(x) (x).begin(),(x).end()
#define lbd(x,y) (lower_bound(all(x),y)-(x).begin())
#define ubd(x,y) (upper_bound(all(x),y)-(x).begin())
mt19937 rng(123);
long long rand(long long x,long long y){return rng() % (y+1-x) + x; }
string to_string(char c){string s(1,c);return s;}
using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>;
#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (306)
ll n, t, mp[MAXN], memo[102][102][102][3][2], mod=1e9+7;
ll common(vector<ll> x,vector<ll> y){
mmst(mp,0);
for(auto i:x) ++mp[i];
for(auto i:y) ++mp[i];
ll co = 0; FOR(i,1,3*n) if(mp[i]>1) ++ co;
return co;
}
ll dp(ll d01,ll d02,ll d12,ll turn,bool gone){
if(min({d01, d02, d12}) < 0) return 0;
if(d01==0&&d02==0&&d12==0)return 1;
if(~memo[d01][d02][d12][turn][gone]) return memo[d01][d02][d12][turn][gone];
ll&ans=memo[d01][d02][d12][turn][gone]=0;
if(turn == 0){
ans=(dp(d01-1, d02, d12, 1, 1) * d01 % mod + dp(d01, d02-1, d12+1, 1, gone) * d02 % mod) % mod;
}else if(turn == 1){
ans=(dp(d01, d02, d12-1, 2, 1) * d12 % mod + dp(d01-1, d02+1, d12, 2, gone) * d01 % mod) % mod;
}else{
ans=(dp(d01, d02-1, d12, 0, 0) * d02 % mod + (gone ? dp(d01+1, d02, d12-1, 0, 0) * d12 % mod : 0)) % mod;
}
return ans;
}
int main(){
mmst(memo,-1);
FAST
cin>>n>>t;
while(t--){
vector<vector<ll>> A(3, vector<ll>(2*n, 0));
FOR(j,0,2) FOR(i,0,2*n-1) cin>>A[j][i];
FOR(j,0,2){
mmst(mp,0);
FOR(i,0,2*n-1){
++ mp[A[j][i]];
}
vector<ll> B;
FOR(i,0,2*n-1) if(mp[A[j][i]]==1) B.eb(A[j][i]);
A[j]=B;
}
cout<<dp(common(A[0], A[1]), common(A[0], A[2]), common(A[1], A[2]), 0, 0)<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
50172 KB |
Output isn't correct |
| 2 |
Incorrect |
26 ms |
50176 KB |
Output isn't correct |
| 3 |
Incorrect |
31 ms |
50176 KB |
Output isn't correct |
| 4 |
Incorrect |
28 ms |
50176 KB |
Output isn't correct |
| 5 |
Incorrect |
46 ms |
50168 KB |
Output isn't correct |
| 6 |
Runtime error |
126 ms |
101500 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
113 ms |
101496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
115 ms |
101496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
123 ms |
101596 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
111 ms |
101496 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
