Submission #514633

#TimeUsernameProblemLanguageResultExecution timeMemory
514633kshitij_sodaniNoM (RMI21_nom)C++14
100 / 100
134 ms31664 KiB
//#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...