// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 105
#define maxx 1005
#define mod 1000000007
ll n;
ll a[3*maxn];
ll b[3*maxn];
ll c[3*maxn];
ll dp[2*maxn][2*maxn][2*maxn][4][2];
ll fact[3*maxn];
ll add(ll x,ll y){
x+=y;
if(x<0){
x%=mod;
x+=mod;
}else{
if(x>=mod) x%=mod;
}
return x;
}
ll mul(ll a,ll b){
ll ans = (a*b)%mod;
if(ans<0) ans+=mod;
return ans;
}
ll reshi(ll ab,ll bc,ll ca,ll muv,bool bio){
if(ab+bc==0||bc+ca==0||ca+ab==0) return fact[max({ab,bc,ca})];
if(dp[ab][bc][ca][muv][bio]!=-1) return dp[ab][bc][ca][muv][bio];
ll ans = 0;
if(muv==1){
if(ab) ans = add(ans,mul(ab,reshi(ab-1,bc,ca,2,1)));
if(ca) ans = add(ans,mul(ca,reshi(ab,bc+1,ca-1,2,bio)));
}else if(muv==2){
if(bc) ans = add(ans,mul(bc,reshi(ab,bc-1,ca,3,1)));
if(ab) ans = add(ans,mul(ab,reshi(ab-1,bc,ca+1,3,bio)));
}else{
if(ca) ans = add(ans,mul(ca,reshi(ab,bc,ca-1,1,0)));
if(bio){
if(bc) ans = add(ans,mul(bc,reshi(ab+1,bc-1,ca,1,0)));
}
}
return dp[ab][bc][ca][muv][bio] = ans;
}
void tc(){
for(ll i = 0;i<maxn;i++) for(ll j = 0;j<maxn;j++) for(ll k = 0;k<maxn;k++) for(ll e = 0;e<4;e++) for(ll r = 0;r<2;r++) dp[i][j][k][e][r] = -1;
for(ll i = 1;i<=3*n;i++) a[i] = b[i] = c[i] = 0;
for(ll i = 1;i<=2*n;i++){
ll x; cin >> x;
a[x]++;
if(a[x]==2) a[x] = 0;
}
for(ll i = 1;i<=2*n;i++){
ll x; cin >> x;
b[x]++;
if(b[x]==2) b[x] = 0;
}
for(ll i = 1;i<=2*n;i++){
ll x; cin >> x;
c[x]++;
if(c[x]==2) c[x] = 0;
}
ll ab = 0,bc = 0,ca = 0;
for(ll i = 1;i<=3*n;i++){
if(a[i]&&b[i]) ab++;
if(c[i]&&b[i]) bc++;
if(a[i]&&c[i]) ca++;
}
ll cnta = 0,cntb = 0,cntc = 0;
for(ll i = 1;i<=3*n;i++) cnta+=a[i];
for(ll i = 1;i<=3*n;i++) cntb+=b[i];
for(ll i = 1;i<=3*n;i++) cntc+=c[i];
if(cnta>0) cout<<reshi(ab,bc,ca,1,0)<<endl;
else cout<<reshi(ab,bc,ca,2,0)<<endl;
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
fact[0] = 1;
for(ll i = 1;i<3*maxn;i++) fact[i] = mul(fact[i-1],i);
int t; cin >> n >> t;
while(t--) tc();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
66 ms |
116556 KB |
Output is correct |
| 2 |
Correct |
104 ms |
116628 KB |
Output is correct |
| 3 |
Correct |
90 ms |
116612 KB |
Output is correct |
| 4 |
Correct |
89 ms |
116556 KB |
Output is correct |
| 5 |
Correct |
194 ms |
116632 KB |
Output is correct |
| 6 |
Incorrect |
255 ms |
116644 KB |
Output isn't correct |
| 7 |
Incorrect |
294 ms |
116648 KB |
Output isn't correct |
| 8 |
Incorrect |
370 ms |
116688 KB |
Output isn't correct |
| 9 |
Incorrect |
421 ms |
116772 KB |
Output isn't correct |
| 10 |
Incorrect |
550 ms |
116660 KB |
Output isn't correct |
