Submission #1119083

#TimeUsernameProblemLanguageResultExecution timeMemory
1119083andrei_iorgulescuNoM (RMI21_nom)C++14
100 / 100
425 ms31820 KiB
#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;
                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;
}
#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...