Submission #509804

#	Time	Username	Problem	Language	Result	Execution time	Memory
509804		hotboy2703	NoM (RMI21_nom)	C++14	100 / 100	125 ms	33180 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
const long long maxn = 2000;
long long fac[maxn * 2 + 100];
long long fiv[maxn * 2 + 100];
long long ml(long long x, long long y){
    return (x * y) % MOD;
}
long long pow_mod(long long x,long long y){
    if (y == 0)return 1;
    long long r = pow_mod(x,y/2);
    r = ml(r,r);
    if (y % 2)r = ml(r,x);
    return r;
}
long long dp[maxn + 100][maxn + 100];
long long choose(long long k,long long n){
    return ml(ml(fac[n],fiv[k]),fiv[n - k]);
}

long long n,m;
int main(){

    //freopen("NOM.INP","r",stdin);
    //freopen("NOM.OUT","w",stdout);
    fac[0] = 1;
    for (long long i = 1;i <= 2 * maxn;i ++){
        fac[i] = ml(fac[i-1],i);
    }
    fiv[maxn * 2] = pow_mod(fac[2 * maxn],MOD - 2);
    for (long long i = maxn * 2 - 1;i >= 0;i --){
        fiv[i] = ml(fiv[i + 1],i + 1);
    }
    cin>>n>>m;
    dp[0][0] = 1;
    dp[0][1] = 0;
    for (long long i = 1;i <= m;i ++){
        long long am;
        if (i <= (2 * n) % m){
            am = (2 * n) / m + 1;
        }
        else{
            am = (2 * n) / m;
        }
        long long buck = am / 2;
        for (long long j = 0;j <= n;j ++){
            for (long long k = 0;k <= j && k <= buck;k ++){
                dp[i][j] += ml(ml(ml(dp[i - 1][j - k], choose(k * 2,am)),fac[k*2]),fiv[k]);
                dp[i][j] %= MOD;
            }
        }
    }
    long long ans = 1;
    for (long long i = 1;i <= 2 * n;i ++){
        ans = ml(ans,i);
    }
    for (long long j = 1;j <= n;j ++){
        //cout<<dp[m][j]<<' ';

        if (j % 2){
            ans -= ml(fac[j],ml(ml(choose(j,n),dp[m][j]),fac[2 * (n - j)])) + MOD;

        }
        else{
                ans += ml(fac[j],ml(ml(choose(j,n),dp[m][j]),fac[2 * (n - j)]));
        }
        ans %= MOD;
    }
    cout<<(ans + MOD) % MOD;
    return 0;
}

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