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; }