ABC154 - F - Many Many Paths

atcoder.jp

概要

f(x, y) := 1回の行動でx+1 or y+1しかできないときに、(0, 0)から(x, y)まで行く場合の数
と定める。r1, c1, r2, c2が与えられる。 r1 <= i <= r2, c1 <= j <= c2を満たすすべての(i, j)について、f(i, j)を計算しその和を10^9+7で割ったあまりを求めよ。

制約：　1 <= c1 < c2 <= 10^6, 1 <= r1 < r2 <= 10^6

ACするまで

1. コンビネーションの足し算じゃん。碁盤目を書いて足してみる。
2. パスカルの三角形っぽく攻めてみる。
3. どちらのアプローチも失敗して順位がただ下がるのを見るだけの人になる。終了

---

4. 様々な解法があり、良問の宝庫。いろいろ学べてAC！

考察

この記事は、けんちょんさんの次の記事の補足になる。書かれた部分のオーバーラップをする気すら起きない素晴らしい記事を書いたけんちょんさんに深い感謝の念を示す。ありがとう！

drken1215.hatenablog.com

というわけで、以上の記事に網羅されてないような解法についていくつか紹介する。主に紹介するのは3つである。そのうちの2つはギャグです。

形式的べき級数その2

形式的べき級数から導出するやり方としては、けんちょんさんの記事の方がメジャーで分かりやすいが、競プロ友のhotman(@hotmanww)の話を聞いて考え出した導出法も奇想天外ながらも形式的べき級数をうまく利用したものなので、ここで紹介する。

最初に書かれてる式変形は、

を満たすようなの数の組み合わせの場合の数

と等しく、そのような式になるのは高校数学の簡単な組み合わせでわかる。参考資料として2つのページを載せる。

maspyさんの記事

maspypy.com

これの「分割数と形式的べき級数」の章に当たる。

僕の記事

sen-comp.hatenablog.com

これの「玉を区別しない　箱を区別する　個数は無制限」の章に当たる。

DEGwerは偉大解

今回の式変形、実はかの有名なDEGwerさん作の数え上げPDFにも書かれている。
これの14章「二項係数のテクニック」(p30)の3つ目の式に当たる。
やっぱりDEGwerは神。

Wolfram Alpha解

www.wolframalpha.com

は？

突っ込むとできます。Wolfram Aplhaは神。ちなみに同じような式でも次のように突っ込むとうまくできません。
www.wolframalpha.com

ACソースコード：

これらの考察によって、O(N)に落とした解法
Submission #10026164 - AtCoder Beginner Contest 154

実は、対象を入れ替えると同じ操作をもう一度行えて、O(1)のWolfram Alphaと同じ回答にもなる。
Submission #10026297 - AtCoder Beginner Contest 154

一言

ギャグ重めで記事を書いた。Wolfram Alphaがは？すぎてすべてが終わってしまった。