Submission #509594

#	Time	Username	Problem	Language	Result	Execution time	Memory
509594		phamhoanghiep	NoM (RMI21_nom)	C++14	100 / 100	133 ms	15896 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int maxn=2002;
const int mod=1e9+7;
int fact[2*maxn];
int invf[2*maxn];
int dp[maxn][maxn];
int n,m;
int Mul(int a, int b) {
    return 1ll*a*b%mod;
}
int Add(int a, int b) {
    if(a+b>=mod) return a+b-mod;
    return a+b;
}
int Bpow(int a, int b) {
    int res=1;
    int cur=a;
    while(b) {
        if(b&1) res=Mul(res,cur);
        cur=Mul(cur,cur);
        b/=2;
    }
    return res;
}
void init() {
    fact[0]=fact[1]=1;
    invf[0]=invf[1]=1;
    for(int i=2 ; i<2*maxn ; i++) {
        fact[i]=Mul(fact[i-1],i);
        invf[i]=Bpow(fact[i],mod-2);
    }
}
int C(int k, int n) {
    if(k>n) return 0;
    return Mul(fact[n],Mul(invf[n-k],invf[k]));
}
signed main() {
    cin>>n>>m;
    init();
    dp[0][0]=1;
    int rem=(2*n)%m;
    for(int i=1 ; i<=m ; i++) {
        int n_i=(2*n)/m+(i<=rem);
        for(int j=0 ; j<=n ; j++) {
            for(int k=0 ; 2*k<=n_i&&k<=j ; k++) {
                int add=dp[i-1][j-k];
                add=Mul(add,fact[n_i]); add=Mul(add,invf[n_i-2*k]);
                add=Mul(add,C(k,j));
                dp[i][j]=Add(dp[i][j],add);
            }
        }
    }
    int ans=fact[2*n];
    for(int i=1 ; i<=n ; i++) {
        int add=Mul(C(i,n),dp[m][i]);
        add=Mul(add,fact[2*n-2*i]);
        if(i&1) {
            ans-=add;
            if(ans<0) ans+=mod;
        }
        else {
            ans+=add;
            if(ans>=mod) ans-=mod;
        }
    }
    cout<<ans;
}

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