Atcoder Grand Contest 002 F. Leftmost Ball

Atcoder Grand Contest 002 F. Leftmost Ball

F: Leftmost Ball - AtCoder Grand Contest 002 | AtCoder

感想

前半の考察はできたが、あとはなにも手を動かせなかった。
順序制限のある組み合わせの問題であることから、各数を頂点と見たグラフに落とし込み、そのトポロジカルソートの個数を求めることと等価であるところまで詰める考え方が、個人的におもしろかった。

解法

$\ n\ $個の$\ 0\ $と$\ k - 1\ $個の各数を並べる問題。左から見て初めて現れる数は$\ 1, 2, ..., n\ $となっているものとして、最後に$\ n!\ $をかける。$\ 0\ $が出現するたびに、並べることができる数が増加する。

editorialにある図を参考にして適当にdpすると答えが出る。「$\ B\ $の左側には必ず$\ A\ $が無ければならない」などというような制限のもとで順列を考えるときにはこのように考えるのが有効なのだろう（それはそう）。

組み合わせについては、最大$\ n * k\ $くらいまで大きくなるので、いつもの組み合わせのやつ（？）が使えないので、あらかじめfactとinvfactを求めておく方法をとる。invfactについては、$\ \cfrac {1} {x !} = \cfrac {1} {(x + 1)!} * (x + 1)\ $なので、大きい方から再帰的に求めらる。

組み合わせのライブラリがまた長くなった。。。

実装

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

static const int MOD = 1000000007;

long long inv(long long a) {
        long long res = 1;
        long long n = MOD - 2;
        while (n > 0) {
                if (n & 1) res = res * a % MOD;
                a = a * a % MOD;
                n >>= 1;
        }
        return res;
}

long long fact[4040404];
long long invfact[4040404];

void init() {
        fact[0] = 1;
        for (int i = 1; i < 4040404; i ++) fact[i] = (fact[i - 1] * i) % MOD;
        invfact[4040403] = inv(fact[4040403]);
        for (int i = 4040402; i >= 0; i --) invfact[i] = (invfact[i + 1] * (i + 1)) % MOD;
}

long long nCr(long long n, long long r) {
        if (n < r) return 0;
        if (n - r < r) r = n - r;
        return fact[n] * invfact[n - r] % MOD * invfact[r] % MOD;
}

long long dp[2020][2020];

void solve() {
        init();
        int n, k;
        cin >> n >> k;
        if (k == 1) {
                cout << 1 << endl;
                return;
        }
        memset(dp, 0, sizeof dp);
        dp[0][1] = 1LL;
        for (int i = 0; i <= n; i ++) {
                for (int j = i; j <= n; j ++) {
                        if (i != 0) dp[i][j] = dp[i - 1][j]; 
                        if (i != j) {
                                long long a = nCr(i + j * (k - 1) - 1, k - 2);
                                dp[i][j] = (dp[i][j] + dp[i][j - 1] * a % MOD) % MOD;
                        }
                }
        }
        cout << dp[n][n] * fact[n] % MOD << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}