Submission #870522

---

Source Code Expand

# pragma comment(linker, "/STACK: 2000000")
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n';
# define p2(v) cerr << #v << " = " << (complex < int > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vll vector < ll >
# define pii pair < int , int >
const int mod = 1e9 + 7;
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n,k;
    fi>>n>>k;
    if (k == 1) return puts("1") * 0;
    static int f[1 << 23];
    static int c[1 << 23];
    auto C = [&](auto n,auto k)
    {
        if (!(0 <= k && k <= n)) return 0;
        int ans = (1ll * f[n] * c[n - k]) % mod;
        ans = (1ll * ans * c[k]) % mod;
        return ans;
    };
    auto pow = [&](auto a,auto b,auto mod)
    {
        int ans = 1;
        while (b)
        {
            if (b&1)
                ans = (1ll * ans * a) % mod;
            a = (1ll * a * a) % mod;
            b /= 2;
        }
        return ans;
    };
    f[0] = c[0] = 1;
    for (int i = 1;i <= 5e6;++i)
        f[i] = (1ll * f[i - 1] * i) % mod;
    const int MAX = 5e6;
    c[MAX] = pow(f[MAX],mod - 2,mod);
    for (int i = MAX - 1;i;--i)
        c[i] = (1ll * c[i+1] * (i + 1)) % mod;
    static int dp[2005][2005];
    dp[0][0] = 1;
    for (int i = 1;i <= n;++i)
        for (int j = 0;j <= i;++j)
        {
            if (j)
                (dp[i][j] += dp[i][j-1]) %= mod;
            dp[i][j] = (dp[i][j] + 1ll * C(j * k + (i - j - 1) * (k - 1) + k - 2,k - 2) * dp[i-1][j]) % mod;
        }
    fo << (1ll * dp[n][n] * f[n]) % mod << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}

Submission Info

Judge Result