Submission #1119192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119192		MateiKing80	NoM (RMI21_nom)	C++14	100 / 100	282 ms	63048 KiB

Main

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
using ll = long long;

ll lgpow(int b, int e)
{
    if(!e)
        return 1;
    ll x = lgpow(b, e >> 1);
    if(e & 1)
        return x * (x * b % mod) % mod;
    return x * x % mod;
}

const int N = 2000;

ll dp[N + 5][2 * N + 5];
ll fact[2 * N + 5], inv[2 * N + 5];

void precalc()
{
    fact[0] = 1;
    for(int i = 1; i <= 2 * N; i ++)
        fact[i] = fact[i - 1] * i % mod;
    inv[2 * N] = lgpow(fact[2 * N], mod - 2);
    for(int i = 2 * N; i; i --)
        inv[i - 1] = inv[i] * i % mod;
}

int comb(int k, int n)
{
    if(k < 0 || k > n || n < 0)
        return 0;
    return fact[n] * inv[k] % mod * inv[n - k] % mod;
}

signed main()
{
    precalc();
    int n, m;
    cin >> n >> m;
    dp[0][0] = 1;
    for(int i = 1; i <= m; i ++)
    {
        int nr = 0;
        if(i == 1)
            nr = (2 * n) / m;
        else
            for(int j = i - 1; j <= 2 * n; j += m)
                nr ++;
        for(int j = 0; j <= 2 * n; j ++)
            for(int k = 0; k <= min(j, nr); k ++)
                dp[i][nr + j - 2 * k] += dp[i - 1][j] * (fact[j] * inv[j - k] % mod) % mod * comb(k, nr),
                dp[i][nr + j - 2 * k] %= mod;
    }
    cout << lgpow(2, n) * dp[m][0] % mod * fact[n] % mod;
}

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