Submission #640519

#	Time	Username	Problem	Language	Result	Execution time	Memory
640519		Tenis0206	NoM (RMI21_nom)	C++11	100 / 100	33 ms	500 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Mod = 1e9 + 7;
const int vmax = 1e4;

int n,m;

int fact[vmax + 5], invfact[vmax + 5];

int dp[2005],aux[2005];

int nr[2005];

int lgput(int a, int b)
{
    int p = 1;
    while(b)
    {
        if(b % 2 == 0)
        {
            b/=2;
            a = 1LL * a * a % Mod;
        }
        else
        {
            --b;
            p = 1LL * p * a % Mod;
        }
    }
    return p;
}

int invmod(int x)
{
    return lgput(x,Mod-2) % Mod;
}

int comb(int n, int k)
{
    return 1LL * fact[n] * invfact[k] % Mod * invfact[n - k] % Mod;
}

int aranj(int n, int k)
{
    return 1LL * fact[n] * invfact[n - k] % Mod;
}

void precalc()
{
    fact[0] = 1;
    for(int i=1;i<=vmax;i++)
    {
        fact[i] = 1LL * fact[i-1] * i % Mod;
    }
    invfact[vmax] = invmod(fact[vmax]);
    for(int i=vmax-1;i>=0;i--)
    {
        invfact[i] = 1LL * invfact[i + 1] * (i + 1) % Mod;
    }
}

void calc_dp()
{
    int nr_tot = (2 * n) / m;
    int rest = (2 * n) % m;
    for(int r=0;r<m;r++)
    {
        nr[r] = nr_tot;
        if(r<=rest && r!=0)
        {
            ++nr[r];
        }
    }
    for(int i=0;2*i<=nr[0];i++)
    {
        dp[i] = aranj(nr[0],2*i) * invfact[i] % Mod;
    }
    int Max = nr[0] / 2;
    for(int r=1;r<m;r++)
    {
        for(int i=0;i<=Max;i++)
        {
            aux[i] = 0;
        }
        for(int i=0;i<=Max;i++)
        {
            for(int j=0;2*j<=nr[r] && i+j<=Max+nr[r]/2;j++)
            {
                aux[i + j] += dp[i] * aranj(nr[r],2*j) % Mod * invfact[j] % Mod;
                aux[i + j] %= Mod;
            }
        }
        for(int i=0;i<=n;i++)
        {
            dp[i] = aux[i];
        }
        Max += nr[r] / 2;
    }
}

signed main()
{
    cin>>n>>m;
    precalc();
    calc_dp();
    int rez = 0;
    for(int i=0;i<=n;i++)
    {
        if(i % 2 == 0)
        {
            rez += dp[i] * fact[2 * (n - i)] % Mod * aranj(n,i) % Mod;
            rez %= Mod;
        }
        else
        {
            rez -= dp[i] * fact[2 * (n - i)] % Mod * aranj(n,i) % Mod;
            rez %= Mod;
            if(rez < 0)
            {
                rez += Mod;
            }
        }
    }
    cout<<rez<<'\n';
    return 0;
}

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