Submission #1181010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181010		12345678	NoM (RMI21_nom)	C++20	100 / 100	66 ms	23108 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=2e3+5, mod=1e9+7;

ll n, m, groupsz[nx], dp[nx][nx], qs[nx], f[nx], inv[nx], res;

ll binpow(ll a, ll x)
{
    if (x==0) return 1;
    ll tmp=binpow(a, x/2);
    tmp=(tmp*tmp)%mod;
    if (x%2) return (tmp*a)%mod;
    return tmp;
}

ll npr(ll n, ll k)
{
    return (f[n]*inv[n-k])%mod;
}

ll ncr(ll n, ll k)
{
    return (npr(n, k)*inv[k])%mod;
}
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    f[0]=1;
    for (int i=1; i<=n; i++) f[i]=(f[i-1]*i)%mod;
    inv[n]=binpow(f[n], mod-2);
    for (int i=n-1; i>=0; i--) inv[i]=(inv[i+1]*(i+1))%mod;
    for (int i=1; i<=2*n; i++) groupsz[(i%m)+1]++;
    dp[0][0]=1;
    for (int g=1; g<=m; g++)
    {
        qs[g]=qs[g-1]+groupsz[g];
        //cout<<"size "<<g<<' '<<groupsz[g]<<'\n';
        for (int cur=1; cur<=n; cur++)
        {
            for (int lst=max(0ll, cur-groupsz[g]); lst<=cur; lst++)
            {
                //if (cur-lst>groupsz[g]) continue;
                ll open=2*lst-qs[g-1], used=cur-lst, close=groupsz[g]-used;
                //cout<<"lst "<<lst<<'\n';
                //cout<<"open "<<open<<' '<<used<<' '<<close<<'\n';
                if (open<close) continue;
                dp[g][cur]=(dp[g][cur]+((ncr(groupsz[g], used)*npr(open, close))%mod)*dp[g-1][lst])%mod;
            }
            //cout<<"dp "<<g<<' '<<cur<<' '<<dp[g][cur]<<'\n';
        }
    }
    res=(((dp[m][n]*f[n])%mod)*binpow(2, n))%mod;
    cout<<res;
}

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