Submission #259638

#	Time	Username	Problem	Language	Result	Execution time	Memory
259638		errorgorn	Fishing Game (RMI19_fishing)	C++14	100 / 100	159 ms	222584 KiB

fishing

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

int n,tc;
int occ[305];

ll memo[305][305][305];
ll dp(int a,int b,int c){
	if (a<0 || b<0 || c<0) return 0;
	
	if (memo[a][b][c]!=-1) return memo[a][b][c];
	if (a==0 && b==0 && c==0) return memo[a][b][c]=1;
	else if (a==0 && c==0) return memo[a][b][c]=(b*dp(a,b-1,c))%MOD;
	
	ll res=0;
	
	res=(res+a*b%MOD*c%MOD*dp(a-1,b-1,c-1))%MOD;
	
	res=(res+a*b%MOD*(b-1)%MOD*dp(a,b-2,c))%MOD;
	res=(res+a*(a-1)%MOD*(c+1)%MOD*dp(a-2,b,c))%MOD;
	res=(res+c*(b+1)%MOD*(c-1)%MOD*dp(a,b,c-2))%MOD;
	
	res=(res+a*(a-1)%MOD*b%MOD*dp(a-1,b-1,c+1))%MOD;
	res=(res+c*(b+1)%MOD*b%MOD*dp(a+1,b-1,c-1))%MOD;
	res=(res+c*a%MOD*c%MOD*dp(a-1,b+1,c-1))%MOD;
	
	return memo[a][b][c]=res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	memset(memo,-1,sizeof(memo));
	cin>>n>>tc;
	
	while (tc--){
		memset(occ,-1,sizeof(occ));
		int t;
		
		int a=0,b=0,c=0;
		
		rep(x,0,n*2){
			cin>>t;
			if (occ[t]==-1) occ[t]=0;
		}
		rep(x,0,n*2){
			cin>>t;
			if (occ[t]==-1) occ[t]=1;
			else if (occ[t]==0) a++;
		}
		rep(x,0,n*2){
			cin>>t;
			if (occ[t]==-1) occ[t]=2;
			else if (occ[t]==0) c++;
			else if (occ[t]==1) b++;
		}
		
		//cout<<a<<" "<<b<<" "<<c<<endl;
		cout<<dp(a,b,c)<<endl;
	}
	
}

• Subtask 1: 100 / 100