鹿島建設プログラミングコンテスト2020 (ARC110) D - Binomial Coefficient is Fun 解説

数学問エスパーが成功したときほど気持ちいい瞬間はありません。

問題リンク

https://atcoder.jp/contests/arc110/tasks/arc110_d

問題概要

長さ $N$ の非負整数列 $A$ があります。長さ $N$ 、総和 $M$ 以下の非負整数列 $B$ 全てについて、 $\displaystyle \prod_{i=1}^{N} \binom{B_i}{A_i}$ の総和を $10^9+7$ で割った余りを出力してください。

制約

$1\le N\le 2000$
$1\le M\le 10^9$
$1\le A_i \le 2000$

考察・解法

直接数え上げは頭が混乱しそうなので、形式的冪級数を用いた考察をしてみます。

以下、 $S=\sum_{i=0}^{N-1}A_i,\ m=M-S=M-\sum A_i$ とします。求めるものは、各二項係数に $m$ を分配したものと考えられます。各二項係数は互いに区別ができるので、 $m$ の分配のしかたは重複組合せで表せると分かります。
ところで、 $m$ 個のものを $N$ 個の箱に分配する方法の通り数は、形式的冪級数を用いて以下のように表せます。

$\displaystyle [x^m] \prod_{i=0}^{N-1}(1+x+x^2+\dots)$

これは $i$ 番目の箱に $x$ の次数個のものを入れる場合の数と解釈できます。
では、 $i$ 番目の箱にものをある個数入れたときの答えへの寄与を $1$ ではなく、二項係数にしましょう。すると、次のように表されます。

$\displaystyle [x^m] \prod_{i=0}^{N-1}\left(\binom{A_i}{A_i}+\binom{A_i+1}{A_i}x+\binom{A_i+2}{A_i}x^2+\dots\right)=[x^m] \prod_{i=0}^{N-1} \sum_{j=0}^{\infty}\binom{A_i+j}{A_i}x^j$

これを簡単な式で表せることができたら答えです。以下、

$\displaystyle f(x,\ A_i)=\sum_{j=0}^{\infty}\binom{A_i+j}{A_i}x^j$

と表すことにします。

さて、これに関して簡単に実験をすると、次のような式が成立するのではないかと予想することができます¹。

$f(x,\ p)f(x,\ q)=f(x,\ p+q+1)$

証明は略しますが難しくはないと思います。
これより、求めたい形式的冪級数は次のように簡単に表されることが分かります。

$\displaystyle \prod_{i=0}^{N-1} \sum_{j=0}^{\infty}\binom{A_i+j}{A_i}x^j=\prod_{i=0}^{N-1}f(x,\ A_i)=f\left(x,\ \sum_{i=0}^{N-1}A_i+N-1\right)$

答えはこの形式的冪級数の $x^i\ (i=0,\ 1,\ \dots,\ m)$ の係数の総和なので、次のようにひとつの二項係数で表されます。

$\displaystyle \sum_{k=0}^{m} [x^k] f\left(x,\ \sum_{i=0}^{N-1}A_i+N-1\right)=\sum_{i=0}^{m}\binom{i+S+N-1}{S+N-1}=\binom{S+N+m}{S+N}=\binom{M+N}{S+N}$

実装

$S+N\le 2000^2+2000$ より、これは二項係数の定義通り計算できます。

実装を展開する

       public void Solve()
        {
            var (n, m) = cin.ReadValue<int, long>();
            var a = cin.ReadLongArray(n);
            m -= a.Sum();
            if(m < 0)
            {
                Console.WriteLine(0);
                return;
            }
 
            long k = a.Sum() + n - 1;
            ModInt ans = 1;
 
            for (int i = 1; i <= k + 1; i++)
            {
                ans *= (m + i);
                ans /= i;
            }
 
            Console.WriteLine(ans);
        }

ACコード: https://atcoder.jp/contests/arc110/submissions/18591839

感想

前回の ARC109-E で実験エスパーが話題になりました。その反省より実験して法則性を見出すのに敏感になっていたのが幸いしました。

また、ちょっと前に maspy さんの形式的冪級数解説記事をざっと読んでどういうものか理解していました。形式的冪級数を考察の手段として使う方法をこの記事で学び、それが早速今回役立ちました。素晴らしい記事をありがとうございます。

maspypy.com

【追記】なお、今回の問題で扱っている内容は「負の二項定理」そのものになります。

maspypy.com

ちなみに、今回のコンテストで無事 AtCoder 青色になれました。色変記事は 12/9 の色変記事アドベントカレンダーにて公開予定です。お楽しみに！

$A_i=1,\ 2$ などのケースで実際に計算すると分かりやすいかもしれません。私はサンプルケース 1 ( $A=(1,\ 2,\ 1)$ ) に関して実験したところ、求めたい冪級数が $1+7x+28x^2+84x^3+\dots$ となり、係数に $\binom{i+6}{6}$ が現れたことから予測がつきました。↩