제출 #259129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259129		handlename	Fishing Game (RMI19_fishing)	C++17	0 / 100	16 ms	24576 KiB

fishing

#include <bits/stdc++.h>
//#include "bingo.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long n,t,p;
int memo[101][101][101][3][2];
long long dp(int ab,int ac,int bc,int guy,bool use){
    //a is 0 and 1, b is 0 and 2, c is 1 and 2
    if (ab==0 && ac==0 && bc==0) return 1;
    if (guy==0){
        if (!use) return 0;
        use=false;
    }
    if (memo[ab][ac][bc][guy][use]!=-1){
        return memo[ab][ac][bc][guy][use];
    }
    long long res=0;
    if (guy==0){
        if (ab+ac==0){
            res=dp(ab,ac,bc,1,use);
            res%=p;
        }
        else {
            if (ab>0) res+=dp(ab-1,ac,bc,1,true)*(long long) ab;
            res%=p;
            if (ac>0) res+=dp(ab,ac-1,bc+1,1,use)*(long long) ac;
            res%=p;
        }
    }
    else if (guy==1){
        if (ab+bc==0){
            res=dp(ab,ac,bc,2,use);
            res%=p;
        }
        else {
            if (bc>0) res+=dp(ab,ac,bc-1,2,true)*(long long) bc;
            res%=p;
            if (ab>0) res+=dp(ab-1,ac+1,bc,2,use)*(long long) ab;
            res%=p;
        }
    }
    else {
        if (ac+bc==0){
            res=dp(ab,ac,bc,0,use);
            res%=p;
        }
        else {
            if (ac>0) res+=dp(ab,ac-1,bc,0,false)*(long long) ac;
            res%=p;
            if (bc>0) res+=dp(ab+1,ac,bc-1,0,false)*(long long) bc;
            res%=p;
        }
    }
    //cout<<a<<' '<<b<<' '<<c<<' '<<guy<<' '<<use<<' '<<res<<'\n';
    return memo[ab][ac][bc][guy][use]=res%p;
}
pair<int,int> arr[301];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    memset(memo,-1,sizeof(memo));
    p=1e9+7;
    while (t--){
        cin>>n;
        for (int i=1;i<=n*3;i++){
            arr[i]=mp(-1,-1);
        }
        for (int i=0;i<3;i++){
            for (int j=0;j<n*2;j++){
                int x;
                cin>>x;
                if (arr[x].first==-1) arr[x].first=i;
                else arr[x].second=i;
            }
        }
        int ab=0,ac=0,bc=0;
        //a is 0 and 1, b is 0 and 2, c is 1 and 2
        for (int i=1;i<=n*3;i++){
            if (arr[i].first==arr[i].second) continue;
            if (arr[i].first>arr[i].second){
                swap(arr[i].first,arr[i].second);
            }
            if (arr[i]==mp(0,1)) ab++;
            else if (arr[i]==mp(0,2)) ac++;
            else bc++;
        }
        //cout<<a<<' '<<b<<' '<<c<<'\n';
        cout<<dp(ab,ac,bc,0,true)<<'\n';
    }
}

• Subtask 1: 0 / 100