Submission #509743

#	Time	Username	Problem	Language	Result	Execution time	Memory
509743		hotboy2703	NoM (RMI21_nom)	C++14	34 / 100	1087 ms	456 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[2][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;
long long cal(long long x){
    for (int j = 1;j <= n;j ++)dp[0][j] = 0;
    dp[0][0] = 1;
    for (long long i = 1;i <= m;i ++){
        bool o = i & 1;
        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 <= x;j ++){
            dp[o][j] = 0;
            for (long long k = 0;k <= j && k <= buck;k ++){
                dp[o][j] += ml(ml(ml(dp[!o][j - k], choose(k * 2,am)),fac[k*2]),choose(k,x-j+k));
                dp[o][j] %= MOD;
            }
        }
    }
    return dp[m & 1][x];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //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]),choose(k,n-j+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 ++){
        if (j % 2){
            ans -= ml(ml(choose(j,n),cal(j)),fac[2 * (n - j)]) + MOD;

        }
        else{
                ans += ml(ml(choose(j,n),cal(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: 0 / 18
• Subtask 5: 0 / 48