Submission #509640

#	Time	Username	Problem	Language	Result	Execution time	Memory
509640		duchung	NoM (RMI21_nom)	C++17	100 / 100	164 ms	165256 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1e9 + 7;
const int N = 4005;

int n , m;
int fact[N] , inv[N] , cnt[N] , pre[N];
int C[N][N] , dp[N][N];

int Add(int x , int y)
{
	return (x + y >= mod ? x + y - mod : x + y);
}

int Sub(int x , int y)
{
	return (x - y < 0 ? x - y + mod : x - y);
}

int Mul(int x , int y)
{
	return x * y % mod;
}

int binpow(int n , int k)
{
	int ret = 1;
	while(k)
	{
		if (k & 1) ret = Mul(ret , n);
		n = Mul(n , n);
		k >>= 1;
	}
	return ret;
}

void build()
{
	fact[0] = 1;
	for (int i = 1 ; i < N ; ++i) fact[i] = Mul(fact[i - 1] , i);
	inv[0] = 1;
	for (int i = 1 ; i < N ; ++i) inv[i] = binpow(fact[i] , mod - 2);

	for (int i = 0 ; i < 2 * n ; ++i) cnt[i % m + 1]++;
	// for (int i = 1 ; i < m ; ++i) pre[i] = pre[i - 1] + cnt[i];

	C[0][0] = 1;
	for (int i = 1 ; i < N ; ++i)
	{
		C[i][0] = 1;
		for (int j = 1 ; j < N ; ++j) C[i][j] = Add(C[i - 1][j] , C[i - 1][j - 1]);
	}
}

signed main()
{
	// freopen("input.inp","r",stdin);
	// freopen("output.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	build();

	dp[0][0] = 1;
	for (int i = 1 ; i <= m ; ++i)
	{
		for (int j = 0 ; j <= n ; ++j)
		{
			for (int k = 0 ; 2 * k <= cnt[i] && k <= j ; ++k)
			{
				int cur = dp[i - 1][j - k];
				cur = Mul(cur , fact[cnt[i]]);
				cur = Mul(cur , inv[cnt[i] - k * 2]);
				cur = Mul(cur , C[j][k]);
				dp[i][j] = Add(dp[i][j] , cur);
			}
		}
	}
	
	int ans = 0;
	for (int j = 0 ; j <= n ; ++j)
	{
		if (j & 1) ans = Sub(ans , Mul(fact[n * 2 - j * 2] , Mul(C[n][j] , dp[m][j])));
		else ans = Add(ans , Mul(fact[n * 2 - j * 2] , Mul(C[n][j] , dp[m][j])));
	}
	cout << ans;
}

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