Submission #1119090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119090		andrei_iorgulescu	NoM (RMI21_nom)	C++14	100 / 100	181 ms	31816 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int modulo = 1e9 + 7;

int n, m;
int a[2005];
int dp[2005][2005];
int f[2005];
int fact[4005], invfact[4005];

int C(int x, int y)
{
    return fact[x] * invfact[y] % modulo * invfact[x - y] % modulo;
}

int lgpow(int x, int y)
{
    int z = 1;
    while (y != 0)
    {
        if (y % 2 == 1)
            z = z * x % modulo;
        x = x * x % modulo;
        y /= 2;
    }
    return z;
}

signed main()
{
    fact[0] = 1;
    for (int i = 1; i <= 4001; i++)
        fact[i] = i * fact[i - 1] % modulo;
    for (int i = 0; i <= 4001; i++)
        invfact[i] = lgpow(fact[i], modulo - 2);
    cin >> n >> m;
    for (int i = 1; i <= 2 * n; i++)
        a[(i - 1) % m + 1]++;
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            for (int q = 0; q <= j and 2 * q <= a[i]; q++)
            {
                int coef = dp[i - 1][j - q];
                //for (int r = j - q + 1; r <= j; r++)
                //    coef = coef * (n - r + 1) % modulo;
                int r = j - q + 1;
                int upb = n - r + 1;
                r = j;
                int lwb = n - r + 1;
                coef = coef * fact[upb] % modulo * invfact[lwb - 1] % modulo;
                coef = coef * C(a[i], 2 * q) % modulo;
                coef = coef * fact[2 * q] % modulo;
                coef = coef * invfact[q] % modulo;
                dp[i][j] = (dp[i][j] + coef) % modulo;
            }
            //cout << i << ' ' << j << ' ' << dp[i][j] << endl;
        }
    }
    for (int i = 0; i <= n; i++)
        f[i] = dp[m][i] * fact[2 * n - 2 * i] % modulo;
    int ans = 0;
    for (int i = 0; i <= n; i++)
    {
        if (i % 2 == 0)
            ans += f[i];
        else
            ans -= f[i];
    }
    ans = (ans % modulo + modulo) % modulo;
    cout << ans;
    return 0;
}

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