2019-01-14

キーエンスプログラミングコンテスト 2019 F - Paper Cutting (赤色, 900 点)

二項係数経路数に帰着数え上げ問題 FPSテク:漸化式の母関数を求める期待値期待値の線形性主客転倒 AtCoder900点 AtCoder 赤色diff ARC-like ARC-F 多項式・FPS(形式的冪級数)

このシンプル設定でこの深み...すごい！！！
$P(n, k)$ や $C(n, k)$ は順列や組合せを表すものとする。

問題概要

長方形の紙があって、水平方向の切れ線が $H$ 箇所、垂直方向の切れ線が $W$ 箇所ある。

$H + W$ 箇所の切れ線から $K$ 箇所選んで順に切って行く $P(H+W, K)$ 通りの方法それぞれについて、「各切断操作における切断直後に紙が何枚に分かれているかを合計したもの」を求め、それを合計したものを $1000000007$ で割ったあまりで求めよ。

制約

$1 \le H, W \le 10^{7}$
$1 \le K \le H+W$

自分の解法

どういう方向性でまとめるか悩んだけど、

水平方向から $h$ 本、垂直方向から $w$ 本の切れ目が入る瞬間、紙の枚数は $(h + 1)(w + 1)$ になる
その瞬間が合算される回数は、 $C(H, h) × C(W, w) × (h + w)! × P(H + W - h - w, H + W - K)$

なので、これの積をとったものを、各 $(h, w)$ について合算すればいいことになる。このままでは $O(HW)$ かかってしまう。色んなまとめ方が考えられるだろうが、 $h + w = k$ についてまとめてみることにした。

h + w = k について式変形

$h + w = k$ について、 $h = 0, 1, 2, \dots, k$ に対して

$C(H, h) × C(W, w) × (h + w)! × P(H + W - h - w, H + W - K) × (h + 1)(w + 1)$

を合算したいということになる。ちょっと変形すると

$C(H, h) × C(W, w) × (h + w)! × P(H + W - h - w, H + W - K) × (h + 1)(w + 1)$
$= \frac{H!W!}{(H+W-K)!} × C(h+w, h) × C(H+W-h-w, H-h) × (h+1)(w+1)$

になることがわかる。 $\frac{(H!)(W!)}{(H+W-K)!}$ は定数なので無視する。 $(h+1)(w+1)$ がなければ、 $C(h+w, h) × C(H+W-h-w, H-h)$ を $h = 0, 1, \dots, k$ に対して合算するのは有名問題で、ヴァンデルモンドの畳み込みとして知られている。

これを知らなくても、「二項係数を経路数としてとらえる」というテクニックを駆使すれば自然に導出することができる。上の式は、下図において、左上から右下までいたる最短経路のうち、 $(h, w)$ を表す赤丸点を通るものの本数を表している。それを下図の赤丸すべてについて足すのだから、その総和は $P(H+W, H)$ になる！！！

f:id:drken1215:20190114043929j:plain

続いて、 $(h+1)(w+1)$ を掛けるとどうなるのかを考える。まず、

$(h+1)(w+1) = hw + (k + 1)$

であることに注目する。 $k+1$ は定数なので、外に出せる。問題は、

$C(h+w, h) × C(H+W-h-w, H-h) × hw$

の部分である。これもちょっと式変形すると、ヴァンデルモンドの畳み込みが使える式になる:

$C(h+w, h) × C(H+W-h-w, H-h) × hw$
$= \frac{(h+w)!}{h!w!} × hw × C(H+W-h-w, H-h)$
$= (h+w)(h+w-1) × \frac{(h+w-2)!}{(h-1)!(w-1)!} × C(H+W-h-w, H-h)$
$= k(k-1) × C(h+w-2, h-1) × C(H+W-h-w, H-h)$

これを $h = 0, 1, \dots, k$ について足しあわせたら、 $k(k-1) × C(H+W-2, H-1)$ になる。

以上より、 $h + w = k$ についての総和は

$\frac{H!W!}{(H+W-K)!} × ( (k+1)C(H+W, H) + k(k-1)C(H+W-2, H-1) )$

となることがわかった。あとはこれを $k = 1, 2, \dots, K$ について合計すればいい。実装は短く済む。

#include <iostream>
using namespace std;

const int MAX = 21000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main() {
    COMinit();
    long long H, W, K; cin >> H >> W >> K;
    long long res = 0;
    for (long long k = 1; k <= K; ++k) {
        long long tmp1 = (k + 1) * COM(H + W, H) % MOD;
        long long tmp2 = k * (k - 1) % MOD * COM(H + W - 2, H - 1) % MOD;
        long long tmp = (tmp1 + tmp2) % MOD * fac[H] %  MOD * fac[W] % MOD * finv[H+W-K] % MOD;
        res = (res + tmp) % MOD;
    }
    cout << res << endl;
}

解法 2: 母関数

強そう。コンビネーションの式の $i + j$ の値を固定したときの畳み込み計算は、母関数の世界に移して考えると多項式の積 (の $i + j$ 次の係数) を求める問題になるので、計算が機械的に楽になるみたい。

いつか使うかもということで覚えておきたい。

kobae さんの解説

解法 3: カウントするときのまとめ方が違う解法

切り取り線を入れる順序 $P(H+W, K)$ 通りそれぞれについて、各フェーズにおける切り取り線を「使った」「まだ使っていない」を $1, 0$ で管理して、 $x_i = 0$ or $1$ , $y_j = 0$ or $1$ といったように表すことにすると、 $k$ 個目の切り取り線が入った段階で加算される値は

$(x_1 + x_2 + \dots + x_H + 1)(y_1 + y_2 + \dots + y_W + 1)$
$= \sum_{i, j} x_i y_j + k + 1$

となる。...とここまでは、切り取り線を入れる順番 $P(H+W, K)$ 通りのうちの 1 つを固定する方向性で考えていたが、ここで切り取り線のペア $(i, j)$ を固定して考える方向にシフトしてみる。

$k + 1$ の項の方はまとめて処理してしまえる。切り取り線を入れる順序は $P(H+W, K)$ 通りあるので、

$(k+1)P(H+W, K)$

になる。 $x_i y_j$ の方は、 $x_i = y_j = 1$ のとき、すなわち水平線 $i$ と垂直線 $j$ とが両方そろった後からは $1$ が加算され続けることとなる。 $P(H + W, K)$ 通りの切り取り順序のうち、 $k$ 個目の切り取り線が入った段階で $(i, j)$ が切り取られているようなものの個数を数えてあげればよくて (ここのところは「期待値の線型性」を用いていると考えてもいい)、