Submission #1181004

#TimeUsernameProblemLanguageResultExecution timeMemory
118100412345678NoM (RMI21_nom)C++20
0 / 100
0 ms324 KiB
#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];

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=0; lst<=cur; lst++)
            {
                if (cur-lst>groupsz[g]) continue;
                ll open=2*lst-qs[g-1], used=cur-lst, close=groupsz[g]-used;
                //if (lst==cur) 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';
        }
    }
    cout<<(dp[m][n]*f[n])%mod;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...