This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo m,n;
const llo mod=1e9+7;
llo ee(llo aa,llo bb){
if(bb==0){
return 1;
}
llo ac=ee(aa,bb/2);
ac=(ac*ac)%mod;
if(bb%2==1){
ac=(ac*aa)%mod;
}
return ac;
}
llo fac[4002];
llo fac2[4002];
llo cal(llo x,llo y){
llo cur=(fac[x]*fac2[y])%mod;
cur=(cur*fac2[x-y])%mod;
return cur;
}
llo dp[2001][2001];
llo co[2001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
fac[0]=1;
llo ma=4000;
for(llo i=1;i<=ma;i++){
fac[i]=(fac[i-1]*i)%mod;
//cout<<fac[i]<<":";
}
// cout<<endl;
for(llo i=ma;i>=0;i--){
if(i==ma){
fac2[i]=ee(fac[i],mod-2);
}
else{
fac2[i]=(fac2[i+1]*(i+1))%mod;
}
//cout<<fac2[i]<<":";
}
cin>>n>>m;
for(llo j=0;j<2*n;j++){
co[(j%m)+1]++;
}
dp[0][0]=1;
for(llo i=1;i<=m;i++){
for(llo j=0;j<=n;j++){
llo mi=max((j-(co[i]/2)),(llo)0);
for(llo k=j;k>=mi;k--){
llo cur=cal(co[i],j-k)*cal(co[i]-(j-k),j-k);
cur%=mod;
cur=(cur*fac[j-k])%mod;
dp[i][j]=(dp[i][j]+dp[i-1][k]*cur)%mod;
}
}
}
llo ans=fac[2*n];
//cout<<ans<<":"<<endl;
for(llo i=1;i<=n;i++){
llo cur=dp[m][i];
//cout<<i<<":"<<dp[m][i]<<endl;
cur=(cur*cal(n,i))%mod;
cur=(cur*fac[i])%mod;
cur=(cur*fac[2*n-2*i])%mod;
//cout<<i<<","<<cur<<endl;
if(i%2==1){
//cout<<11<<endl;
ans=(ans-cur+mod)%mod;
}
else{
ans=(ans+cur)%mod;
}
//cout<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
# | 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... |