Submission #509584

#	Time	Username	Problem	Language	Result	Execution time	Memory
509584		Rainbowbunny	NoM (RMI21_nom)	C++17	100 / 100	83 ms	384 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 4005;
const int mod = 1e9 + 7;

int Add(int x, int y)
{
    return x + y >= mod ? x + y - mod : x + y;
}

int Sub(int x, int y)
{
    return x - y < 0 ? x - y + mod : x - y;
}

int Mul(int x, int y)
{
    return 1ll * x * y % mod;
}

int BinPow(int n, int k)
{
    int ans = 1, cur = n;
    while(k)
    {
        if(k & 1)
        {
            ans = Mul(ans, cur);
        }
        cur = Mul(cur, cur);
        k >>= 1;
    }
    return ans;
}

int n, m;
int cnt[MAXN], fact[MAXN], ifact[MAXN], dp[2][MAXN];

int C(int n, int k)
{
    return Mul(fact[n], Mul(ifact[k], ifact[n - k]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fact[0] = 1;
    for(int i = 1; i < MAXN; i++)
    {
        fact[i] = Mul(fact[i - 1], i);
    }
    ifact[MAXN - 1] = BinPow(fact[MAXN - 1], mod - 2);
    for(int i = MAXN - 2; i >= 0; i--)
    {
        ifact[i] = Mul(ifact[i + 1], i + 1);
    }
    cin >> n >> m;
    for(int i = 0; i < 2 * n; i++)
    {
        cnt[i % m]++;
    }
    int cur = 0;
    dp[0][0] = 1;
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j <= cur; j++)
        {
            if(dp[0][j])
            {
                for(int newpair = 0; 2 * newpair <= cnt[i]; newpair++)
                {
                    dp[1][j + newpair] = Add(dp[1][j + newpair], Mul(dp[0][j], Mul(fact[cnt[i]], Mul(ifact[cnt[i] - 2 * newpair], C(n - j, newpair)))));
                }
            }
        }
        cur += cnt[i];
        for(int j = 0; j <= cur; j++)
        {
            dp[0][j] = dp[1][j];
            dp[1][j] = 0;
        }
    }
    for(int i = n; i >= 0; i--)
    {
        dp[0][i] = Mul(dp[0][i], fact[2 * n - 2 * i]);
        for(int j = i + 1; j <= n; j++)
        {
            dp[0][i] = Sub(dp[0][i], Mul(C(j, i), dp[0][j]));
        }
    }
    cout << dp[0][0] << '\n';
}

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