Submission #44664500

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)

typedef long long ll;
typedef __int128 lll;
typedef unsigned int uint;
typedef pair<int, int> PII;
typedef unsigned long long ull;

const int I = 2010;
const int N = 4000010;
const int mod = 1e9 + 7;

int n, m; ll fc[N], iv[N], dp[I][I];

inline void init()
{
    fc[0] = iv[0] = iv[1] = 1;
    fro(i, 1, N - 10) fc[i] = fc[i - 1] * i % mod;
    fro(i, 2, N - 10) iv[i] = (mod - 1ll * (mod / i) * iv[mod % i] % mod);
    fro(i, 1, N - 10) iv[i] = iv[i - 1] * iv[i] % mod;
}
inline ll C(int x, int y)
    { return fc[x] * iv[y] % mod * iv[x - y] % mod; }

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    init();
    cin >> n >> m, dp[0][0] = 1;
    fro(i, 1, n)
    {
        fro(j, 0, i)
        {
            if(i > j) dp[i][j] += dp[i - 1][j];
            if(m != 1 && j != 0)
                dp[i][j] += (n - j + 1) * dp[i][j - 1] % mod * C(n * m - i - (m - 1) * (j - 1) - 1, m - 2);
            dp[i][j] %= mod;
        }
    }
    if(m == 1) cout << dp[n][0] << "\n";
    else cout << dp[n][n] << "\n";
    return 0;
}

Submission Info

Judge Result