oj.uz

Submission #514607

# Submission time Handle Problem Language Result Execution time Memory
514607 2022-01-18T09:55:49 Z kshitij_sodani NoM (RMI21_nom) C++14
0 / 100
 1 ms 380 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo m,n;
const llo mod=1e9+7;

llo ee(llo aa,llo bb){
	if(bb==0){
		return 1;
	}
	llo ac=ee(aa,bb/2);
	ac=(ac*ac)%mod;
	if(bb%2==1){
		ac=(ac*aa)%mod;
	}
	return ac;
}
llo fac[4002];
llo fac2[4002];
llo cal(llo x,llo y){
 
	llo cur=(fac[x]*fac2[y])%mod;
	cur=(cur*fac2[x-y])%mod;
	return cur;
}

llo dp[2001][2001];
llo co[2001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	fac[0]=1;
	llo ma=4000;
	for(llo i=1;i<=ma;i++){
		fac[i]=(fac[i-1]*i)%mod;
		//cout<<fac[i]<<":";
	}
//	cout<<endl;
 
	for(llo i=ma;i>=0;i--){
		if(i==ma){
			fac2[i]=ee(fac[i],mod-2);
		}
		else{
			fac2[i]=(fac2[i+1]*(i+1))%mod;
		}
		//cout<<fac2[i]<<":";
	}
	cin>>n>>m;
	for(llo j=0;j<2*n;j++){
		co[(j%m)+1]++;
	}
	dp[0][0]=1;
	for(llo i=1;i<=m;i++){
		for(llo j=0;j<=n;j++){
			llo mi=max((j-(co[i]/2)),(llo)0);
			for(llo k=j;k>=mi;k--){
				llo cur=cal(co[i],j-k)*cal(co[i]-(j-k),j-k);
				cur%=mod;
				dp[i][j]=(dp[i][j]+dp[i-1][k]*cur)%mod;
			}
		}
	}


	llo ans=fac[2*n];
	//cout<<ans<<":"<<endl;
	for(llo i=1;i<=n;i++){
		llo cur=dp[m][i];
		//cout<<i<<":"<<dp[m][i]<<endl;
		cur=(cur*cal(n,i))%mod;
		cur=(cur*fac[i])%mod;
		cur=(cur*fac[2*n-2*i])%mod;
		if(i%2==1){
			ans=(ans-cur+mod)%mod;
		}
		else{
			ans=(ans+cur)%mod;
		}
		
	}
	cout<<ans<<endl;



 
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -