Submission #1213622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213622		Muhammad_Aneeq	NoM (RMI21_nom)	C++20	100 / 100	116 ms	39792 KiB

Main

#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
int const N=4e3+10,mod=1e9+7;
int fac[N],inv[N];
int dp[N][N]={};// fixing j numbers within first 1.....i mod m
int power(int x,int y)
{
	int res=1;
	while (y)
	{
		if (y&1)
			res=(res*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return res;
}
int add(int a,int b)
{
	return ((a+b)%mod+mod)%mod;
}
int mul(int a,int b)
{
	return (a*b)%mod;
}
int nCr(int n,int r)
{
	if (r>n)
		return 0;
	return mul(fac[n],mul(inv[r],inv[n-r]));
}
int nPr(int n,int r)
{
	if (r>n)
		return 0;
	return mul(fac[n],inv[n-r]);
}
inline void solve()
{
	int n,m;
	cin>>n>>m;
	int cnt[m+1]={};
	for (int i=1;i<=2*n;i++)
		cnt[i%m+1]++;
	dp[0][0]=1;
	for (int i=1;i<=m;i++)
	{
		dp[i][0]=1;
		for (int j=1;j<=n;j++)
		{
			for (int k=0;k<=j&&2*k<=cnt[i];k++)
			{
				dp[i][j]=add(dp[i][j],mul(dp[i-1][j-k],mul(nPr(cnt[i],2*k),nCr(j,k))));
			}
		}
	}
	int ans=0;
	int cof=-1;
	for (int i=1;i<=n;i++)
	{
		ans=add(ans,cof*mul(fac[2*(n-i)],mul(nCr(n,i),dp[m][i])));
		cof=-cof;
	}
	ans=add(ans,fac[2*n]);
	cout<<ans<<endl;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    fac[0]=inv[0]=1;
    for (int i=1;i<N;i++)
    {
    	fac[i]=mul(fac[i-1],i);
    	inv[i]=power(fac[i],mod-2);
    }
    int t=1;
    for (int i=1;i<=t;i++)
        solve();
}

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