halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ABC110D - Binomial Coefficient is Fun

競プロ 今日の精進 黄Diff ARC

毎日格上の問題を倒すやつの48日目です。*1

問題リンク

atcoder.jp

問題概要

長さ N の数列 A が与えられるよ。

和が M 以下のすべての数列 B に対して、\prod_{i=1}^{N}\binom{B_i}{A_i} を求めて、その総和を 10^9+7 で割った余りを求めてね。

解法

負の二項定理を使って解くのが簡潔です。

これは、[x^{n}](1-x)^{-r}=\binom{n+r-1}{r-1} というものです。まさに今回使えそうなものです。

とりあえずすべての A に対してやってみると、A の総和を S として [(1-x)^{-(S+N)}] の何項目かまでの総和を求めたいわけです。

とりあえず、総和を求めるのはきついので (1-x) で割って (1-x)^{-(S+N+1)} の何項目かを求めることにします。

結論としては、[x^{M-S}]((1-x)^{-(S+N+1)} を求めればよかったりします。これはいい感じに式変形すれば求まります。

結局、答えは \binom{M+N}{S+N} です。

提出コード

MOD=10**9+7
N,M=map(int,input().split())
A=list(map(int,input().split()))
cnt=sum(A)+N
up=cnt+M-sum(A)
ans=1
#print(cnt,up)
for i in range(cnt):
    ans*=up-i
    ans*=pow(i+1,-1,MOD)
    ans%=MOD
print(ans)

Submission #47346140 - AtCoder Regular Contest 110 (Sponsored by KAJIMA CORPORATION)

感想

mod998244353だと思ってて死ぬほど苦戦した

*1:もとい、FPSウィークの3日目です。