oj.uz

Submission #259638

# Submission time Handle Problem Language Result Execution time Memory
259638 2020-08-08T06:08:22 Z errorgorn Fishing Game (RMI19_fishing) C++14
100 / 100
 159 ms 222584 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 222456 KB Output is correct
2 Correct 114 ms 222388 KB Output is correct
3 Correct 111 ms 222436 KB Output is correct
4 Correct 116 ms 222460 KB Output is correct
5 Correct 122 ms 222456 KB Output is correct
6 Correct 130 ms 222456 KB Output is correct
7 Correct 130 ms 222584 KB Output is correct
8 Correct 135 ms 222584 KB Output is correct
9 Correct 149 ms 222456 KB Output is correct
10 Correct 159 ms 222456 KB Output is correct