Blog

题目

Atcoder

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 4000010, mod = 1e9 + 7;
int n, k, fact[N], invf[N], f[2010][2010];
int qmi(int a, int b) {
    int res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1) res = 1ll * res * a % mod;
    return res;
}
int inv(int x) { return qmi(x, mod - 2); }
int C(int n, int m) { return 1ll * fact[n] * invf[m] % mod * invf[n - m] % mod; }
int main() {
    cin >> n >> k;
    fact[0] = 1, invf[0] = 1;
    if (k == 1) return cout << "1" << endl, 0;
    for (int i = 1; i <= 4000000; i++) 
        fact[i] = 1ll * fact[i - 1] * i % mod, invf[i] = inv(fact[i]);
    for (int i = 0; i <= n; i++) f[i][0] = 1;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= i; j++)
            f[i][j] = (f[i - 1][j] + 1ll * f[i][j - 1] * (n - j + 1) % mod * 
                      C(n * k - i - 1 - (j - 1) * (k - 1), k - 2) % mod) % mod;
    cout << f[n][n] << endl;
    return 0; 
}