Submission #499849

#	Time	Username	Problem	Language	Result	Execution time	Memory
499849		keta_tsimakuridze	NoM (RMI21_nom)	C++14	100 / 100	118 ms	27344 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N = 2000 + 5, mod = 1e9 + 7; // !
int t, dp[N][N], fact[2 * N], invfact[2 * N],x[N],d[2 * N];
int pwr(int u,int v) {
	int ans = 1;
	while(v) {
		if(v % 2) ans = ans * u % mod;
		v /= 2; u = u * u % mod;
	}
	return ans;
}
int A(int a,int b) {
	if(a < 0) return 0;
	if(a < b) return 0;
	return fact[a] * invfact[a - b] % mod;
}
int c(int a,int b) {
	if(a < b || a < 0) return 0;
	return fact[a] * invfact[a - b] % mod * invfact[b] % mod;
}
main(){
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= 2 * n; i++) {
		x[i % m + 1]++;
	}
	fact[0] = invfact[0] = 1;
	for(int i = 1; i <= 2 * n; i++) fact[i] = fact[i - 1] * i % mod,
								invfact[i] = invfact[i - 1] * pwr(i, mod - 2) % mod;
	
	int cur = 0;
	dp[0][0] = 1;
	for(int i = 1; i <= m; i++) {
		for(int j = 0; j <= cur; j++) {
			for(int k = 0; k <= x[i]; k += 2) {
				dp[i][j + k / 2] += dp[i - 1][j] * A(x[i], k) % mod * c(n - j, k / 2) % mod;
				dp[i][j + k / 2] %= mod;
			}
		}
	//	cout << dp[i][2] <<" "<< c[i] << endl;
		cur += x[i];
	//	for(int j = 0; j <= cur; j++) cout<<dp[i][j] <<" "; cout << endl;
	}
	
	for(int i = n; i >= 0; i--) {
		d[i] = dp[m][i] * fact[2 * n - i * 2] % mod; 
		for(int j = i + 1; j <= n; j++) {
			d[i] -=  d[j] * c(j, i) % mod;
			d[i] += mod; d[i] %= mod;
		}
	}
	cout << d[0];
}

Compilation message (stderr)

Main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main(){
      | ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48