Submission #499447

#	Time	Username	Problem	Language	Result	Execution time	Memory
499447		andrei_boaca	NoM (RMI21_nom)	C++17	100 / 100	48 ms	23208 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
/*ifstream fin("num.in");
ofstream fout("num.out");*/
typedef long long ll;
const ll mod=1e9+7;
ll n,m,dp[2005][2005],ans,fact[10005],invfact[10005],nr[10005];
ll pw(ll a, ll b)
{
    ll rez=1;
    while(b)
    {
        if(b&1)
            rez=(rez*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return rez;
}
ll inv(ll a)
{
    return pw(a,mod-2);
}
ll comb(ll a, ll b)
{
    if(a<b)
        return 0;
    ll rez=(fact[a]*invfact[b])%mod;
    rez=(rez*invfact[a-b])%mod;
    return rez;
}
ll aranj(ll a, ll b)
{
    ll rez=comb(a,b);
    rez=(rez*fact[b])%mod;
    return rez;
}
int main()
{
    fact[0]=invfact[0]=1;
    for(ll i=1;i<=10000;i++)
    {
        fact[i]=(fact[i-1]*i)%mod;
        invfact[i]=inv(fact[i])%mod;
    }
    cin>>n>>m;
    for(int i=1;i<=2*n;i++)
        nr[i%m+1]++;
    dp[0][0]=1;
    int suma=0;
    for(int i=1;i<=m;i++)
    {
        suma+=nr[i];
        for(int cur=0;cur<=nr[i]/2;cur++)
        {
            ll x=aranj(nr[i],cur*2);
            for(int tot=cur;tot<=suma/2;tot++)
            {
                ll val=dp[i-1][tot-cur];
                val=(val*x)%mod;
                val=(val*comb(n-tot+cur,cur))%mod;
                dp[i][tot]=(dp[i][tot]+val)%mod;
            }
        }
        //cout<<dp[i][0]<<' ';
    }
    for(int i=0;i<=n;i++)
    {
        ll val=dp[m][i]%mod;
        val=(val*fact[2*n-2*i])%mod;
        if(i%2==1)
        {
            ans-=val;
            if(ans<0)
                ans+=mod;
        }
        else
            ans=(ans+val)%mod;
    }
    cout<<ans;
    return 0;
}

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