Atcoder Grand Contest No.2

コンテストを寝過ごしたので解いた. Dの一般的なテク感すき. きれい. Bが面白い感あった

Eはとりあえずグリッド上を動くゲームなことまではわかったけどあんま考えてない.



Fの方針が解説と少し違ったので書いておこう.

1~Nの1番左のもの(0は無視)がこの順番にあることにして最後にN!をかける. ここで0は出てくる順番に1~Nと結びつけて良いことがわかる

よって0NN..NN (NはK-1個)から始めて, 0(N-1)(N-1)(N-1)...(N-1), ...., 01...1を間に追加していくことが出来ないか考える.

まず上の考察により新しい0は1番左に. そして0iii,,,iを足す時, 1番左のiは, 現在の列の1番左の(i+1)より左, つまり0でない要素のうち1番左より左に入れないといけないことがわかるが, これは先頭の0の個数を状態として持てばOK.

よってdp[i][j]: 大きい方からi種類追加して先頭にj個0があるような条件を満たす並べ方の個数とおくと, 状態はO(N^2)で
遷移も1番左のiを置く場所を全部試すことで遷移O(N), 合計O(N^3)で計算可能. (実際は二項係数を求めるのにlogがつく)

しかし, 係数の式を考えるとそれは新しい1番左のiの場所にしか依存しないことがわかるので, dp[i][j]のjの大きい方から累積和を持っておくことでO(N^2log hoge)で解くことができる.

解説みたいにグラフにするとわかりやすくて感動した.

追記: 1<=i<=Mについてi!の逆元を求めたい時, M!の逆元を求めた後逆向きにかけていけばO(N^2)で計算出来るの今まで気付いてなかった...というわけでO(N^2)で解けます

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const ll MOD = 1000000007;

ll f[4000010];
ll invf[4000010];

ll mod_pow(ll x, ll k)
{
    ll res = 1;
    for (; k; x = x * x % MOD, k /= 2) if (k & 1) res = res * x % MOD;
    return res;
}

ll comb(int n, int k)
{
    if (k < 0 || k > n) return 0;
    return f[n] * invf[k] % MOD * invf[n-k] % MOD;
}

int N, K;

ll dp[2010][2010]; // j = num of front 0
ll acm[2010];

int main() {
    f[0] = invf[0] = 1;

    for (int i = 1; i <= 4000000; ++i) {
	f[i] = f[i-1] * i % MOD;
	invf[i] = mod_pow(f[i], MOD - 2);
    }
    
    cin >> N >> K;

    if (K == 1) {
	puts("1");
	return 0;
    }

    dp[1][1] = 1;

    for (int i = 2; i <= N; ++i) {
	memset(acm, 0, sizeof(acm));

	for (int j = 2000; j >= 0; --j) {
	    acm[j] = (acm[j + 1] + dp[i-1][j]) % MOD;
	}

	for (int j = 1; j <= i; ++j) {
	    int pos = (i - 1) * K - j + 1;

	    ll t = comb(pos + K - 2, K - 2);
	    dp[i][j] = (dp[i][j] + acm[j - 1] * t) % MOD;
	}
    }

    ll ret = 0;
    rep(i, 2010) ret = (ret + dp[N][i]) % MOD;
    ret = ret * f[N] % MOD;

    cout << ret << endl;

    return 0;
}