제출 #1213606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213606		MuhammadSaram	NoM (RMI21_nom)	C++20	100 / 100	34 ms	23112 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 2000 + 1, mod = 1e9 + 7;

int fac[M*2], ifac[M*2], cnt[M], dp[M][M];

int power(int a,int b)
{
	int ans=1;
	for (;b;b>>=1,a=a*a%mod)
		if (b&1) ans=ans*a%mod;
	return ans;
}

int ncr(int n,int k)
{
	return fac[n]*ifac[k]%mod*ifac[n-k]%mod;
}

int per(int x,int k)
{
	return ncr(x,k)*fac[k]%mod;
}

signed main()
{
	fac[0]=ifac[0]=1;
	for (int i=1;i<M*2;i++)
		fac[i]=fac[i-1]*i%mod,ifac[i]=power(fac[i],mod-2);
	
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=2*n;i++)
		cnt[i%m+1]++;
	dp[0][0]=1;
	for (int i=1,su=0;i<=m;su+=cnt[i]/2,i++)
		for (int k=0;k*2<=cnt[i];k++)
		{
			for (int j=0;j<=su;j++)
				dp[i][k+j]+=per(cnt[i],2*k)*dp[i-1][j]%mod*ncr(j+k,j),
				dp[i][k+j]%=mod;
		}
	for (int i=0;i<=n;i++)
		dp[m][i]=dp[m][i]*fac[2*(n-i)]%mod;
	int ans=fac[2*n];
	for (int i=1,mu=-1;i<=n;i++,mu*=-1)
		ans=(ans+ncr(n,i)*dp[m][i]*mu%mod+mod)%mod;
	cout<<ans<<endl;
	
	return 0;
}

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