Submission #644065

#	Time	Username	Problem	Language	Result	Execution time	Memory
644065		k_balint31415	Fishing Game (RMI19_fishing)	C++14	0 / 100	101 ms	64836 KiB

fishing

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;

int n;
ll dp[202][202][202];

ll calc(int a, int b, int c){
    if(a<0 || b<0 || c<0) return 0;
    if(dp[a][b][c] != -1) return dp[a][b][c];

    ll res=0;
    
    if(a>=2) res+=calc(a-2,b,c)*a %mod*(a-1)%mod*(b+1)%mod,res%=mod;
    if(a>=2 && c>=1) res+=calc(a-1,b,c-1)*a%mod*(a-1)%mod*c%mod,res%=mod;

    if(a>=1 && b>=1 && c>=1) res+=calc(a-1,b-1,c-1)*a%mod*b%mod*c%mod,res%=mod;
    if(a>=1 && c>=2) res+=calc(a,b,c-2)*a%mod*c%mod*(c-1)%mod,res%=mod;

    if(a>=1 && b>=1) res+=calc(a-1,b-1,c+1)*a%mod*b%mod*b%mod,res%=mod;

    if(b>=2) res+=calc(a,b-2,c)*b%mod*(c+1)%mod*(b-1)%mod,res%=mod;
    if(b>=1 && c>=1) res+=calc(a+1,b-1,c-1)*b%mod*(c+1)%mod*c%mod,res%=mod;

    dp[a][b][c]=res;
    return res;
}

int arr[302][2];

void solve(){
    for(int i=1;i<=3*n;i++){
        arr[i][0]=arr[i][1]=-1;
    }
    int a,b,c; a=b=c=0;
    for(int i=0;i<3;i++){
        for(int j=1;j<=2*n;j++){
            int x; cin>>x;
            if(arr[x][0]==-1) arr[x][0]=i;
            else arr[x][1]=i;
        }
    }

    for(int i=1;i<=3*n;i++){
        if((arr[i][0]==0 && arr[i][1]==1) || (arr[i][0]==1 && arr[i][1]==0))++a;
        if((arr[i][0]==0 && arr[i][1]==2) || (arr[i][0]==2 && arr[i][1]==0))++b;
        if((arr[i][0]==2 && arr[i][1]==1) || (arr[i][0]==1 && arr[i][1]==2))++c;
    }

    cout << calc(a,b,c) << '\n';
}

int main(){
    for(int i=0;i<202;i++){
        for(int j=0;j<202;j++){
            for(int k=0;k<202;k++){
                dp[i][j][k]=-1;
            }
        }
    }
    dp[0][0][0]=1;

    int tc;
    cin>>n>>tc;
    while(tc--){
        solve();
    }
}

• Subtask 1: 0 / 100