This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
int n,m;
int dp[2005][2005];
int cntr[2005];
int pref[2005];
int fact[10005];
int invf[5005];
int put2[5005];
int put(int a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put((a*a)%MOD,exp/2);
else
return (put((a*a)%MOD,exp/2)*a)%MOD;
}
int comb(int x, int y)
{
if(x<y)
return 0;
return ((((fact[x]*invf[y])%MOD)*invf[x-y])%MOD);
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=2*n;i++)
cntr[i%m+1]++;
fact[0]=1;
put2[0]=1;
for(int i=1;i<=5001;i++)
{
fact[i]=(fact[i-1]*i)%MOD;
put2[i]=(put2[i-1]*2LL)%MOD;
}
invf[5001] = put(fact[5001], MOD-2);
for(int i=5000;i>=0;i--)
invf[i]=(invf[i+1]*(i+1))%MOD;
dp[0][0]=1;
for(int i=1;i<=m;i++)
{
pref[i]=(pref[i-1]+cntr[i])%MOD;
for(int cntp=0;cntp<=pref[i]/2;cntp++)
{
dp[i][cntp]=0;
for(int x=0;x<=min(cntp,cntr[i]);x++)
{
dp[i][cntp] += (((((dp[i-1][cntp-x] * fact[cntr[i]])%MOD) * comb(pref[i-1] - 2*(cntp-x), x))%MOD) * (put2[cntr[i]-x] * comb(n - (pref[i-1] - 2*(cntp-x) - x) - (cntp-x) - x, cntr[i]-x)%MOD))%MOD;
dp[i][cntp] %= MOD;
}
//cout<<i<<" "<<cntp<<" "<<dp[i][cntp]<<"\n";
}
}
cout<<dp[m][n];
return 0;
}
/**
dp[i][cntp] = numarul de moduri de a plasa pietre pe primele i resturi a.i. sa fi plasat cntp perechi de pietre
cntr[i] = nr de pozitii cu restul i
pref[i] = sum(cntr[x]), x = 1..i
dp[i][cntp] = sum(dp[i-1][cntp-x] * fact[cntr[i]] * comb(pref[i-1] - 2*cntp, x) * comb(n - (pref[i-1] - 2*cntp - x) - cntp - x, cntr[i]-x)
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |