Submission #871083

#	Time	Username	Problem	Language	Result	Execution time	Memory
871083		Ahmed57	NoM (RMI21_nom)	C++17	100 / 100	184 ms	32100 KiB

Main

#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
long long fact[10001],inv[10001];
long long fast(long long a,long long b){
    if(b==0)return 1;
    if(b==1)return a;
    long long h = fast(a,b/2);
    h*=h;h%=mod;
    if(b%2)return (h*a)%mod;
    else return h;
}
long long nPr(long long a,long long b){
    return (fact[a]*inv[a-b])%mod;
}
long long nCr(long long a,long long b){
    return (((fact[a]*inv[a-b])%mod)*inv[b])%mod;
}
long long dp[2001][2001];
int n,m;int cnt[2001];
long long solve(int i,int rem){
    if(i==m){
        return fact[rem*2];
    }
    if(dp[i][rem]!=-1)return dp[i][rem];
    long long de = 1;
    long long all =0;
    for(int j = 0;j<=cnt[i]/2;j++){
        all+=(((((solve(i+1,rem-j)*nPr(cnt[i],j*2))%mod)*nCr(rem,j))%mod)*de)%mod;
        all%=mod;
        de*=(mod-1);de%=mod;
    }
    return dp[i][rem] = all;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    memset(dp,-1,sizeof dp);
    fact[0] = 1;inv[0] = fast(fact[0],mod-2);
    for(long long i = 1;i<=1e4;i++){
        fact[i]=(fact[i-1]*i)%mod;
        inv[i]=fast(fact[i],mod-2);
    }
    cin>>n>>m;
    for(int i = 0;i<2*n;i++){
        cnt[i%m]++;
    }
    cout<<solve(0,n)<<endl;
}

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