제출 #1253748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253748		HoriaHaivas	NoM (RMI21_nom)	C++20	100 / 100	163 ms	39180 KiB

Main

#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int range_rng(int l, int r)
{
    return uniform_int_distribution<int>(l,r)(rng);
}

const int mod=1e9+7;
int fact[4005];
int invfact[4005];
int dp[4005][4005];

int lgpow(int x, int p)
{
    int ans,pw,i;
    ans=1;
    pw=x;
    for (i=0; i<=30; i++)
    {
        if (p&(1<<i))
            ans=(ans*pw)%mod;
        pw=(pw*pw)%mod;
    }
    return ans;
}

int invmod(int x)
{
    return lgpow(x,mod-2);
}

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

int nCk(int n, int k)
{
    if (n<k)
        return 0;
    int ans;
    ans=fact[n];
    ans=(ans*invfact[k])%mod;
    ans=(ans*invfact[n-k])%mod;
    return ans;
}

signed main()
{
    //ifstream fin("linii.in");
    //ofstream fout("linii.out");
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,i,j,k,l,ans,nush,sum,x,oke;
    precalc();
    cin >> n >> m;
    dp[0][0]=1;
    sum=0;
    for (i=1; i<=m; i++)
    {
        nush=((2*n)/m)+((i-1)<=((2*n)%m));
        if (i==1)
            nush--;
        sum+=nush;
        for (j=0; j<=sum-nush; j++)
        {
            for (x=0; x<=min(j,nush); x++)
            {
                if ((j+nush-x*2)>=0)
                {
                    dp[i][j+nush-x*2]+=(((((dp[i-1][j]*nCk(nush,x))%mod)*nCk(j,x))%mod)*fact[x])%mod;
                    dp[i][j+nush-x*2]%=mod;
                }
            }
        }
    }
    oke=dp[m][0];
    oke=(oke*fact[n])%mod;
    oke=(oke*lgpow(2,n))%mod;
    cout << oke;
    return 0;
}

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