Submission #826325

---

Source Code Expand

// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>

using namespace std;

#define rep(i, n) for (int i = 0, _n = (int)(n); i < _n; ++i)
#define int long long
const int N = 2005, M = N * N, mod = (int) 1e9 + 7;
int pw(int a, int b) { return b != 0? pw(a * a % mod, b >> 1) * (b & 1? a: 1) % mod: 1; }
int ft[M], fi[M];
int dp[N][N];

int comb(int n, int r) {
    if (r < 0 || n < 0 || n - r < 0) return 0;
    return ft[n] * fi[r] % mod * fi[n - r] % mod;
}
void sadd(int &x, int y) {
    x += y;
    x %= mod;
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ft[0] = fi[0] = 1;
    for (int i = 1; i < M; ++i)
        ft[i] = ft[i - 1] * i % mod;
    fi[M - 1] = pw(ft[M - 1], mod - 2);
    for (int i = M - 2; i >= 0; --i)
        fi[i] = fi[i + 1] * (i + 1) % mod;
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << 1 << endl;
        return 0;
    }
    /*
    if (k == 2) {
        cout << (mod + comb(n + n, n) - comb(n + n, n + 1)) % mod;
        return 0;
    } */
    dp[0][0] = 1;
    for (int p1 = 0; p1 <= n; ++p1)
        for (int p0 = 0; p0 <= p1; ++p0) {
            if (p1) {
                int g = p0 * k + (p1 - p0 - 1) * (k - 1);
                sadd(dp[p1][p0], dp[p1 - 1][p0] * comb(g + 1 + k - 2 - 1, g) % mod);
            }
            if (p0) {
                sadd(dp[p1][p0], dp[p1][p0 - 1]);
            }
        }
    cout << dp[n][n] * ft[n] % mod << endl;
}

Submission Info

Judge Result