Hoi_koro memo

Editorialと異なる解法をしたら更新するblog

codeforces ICM Technex 2018 and Codeforces Round #463 E. Team Work

codeforces

問題

${\sum_{i=1}^n \binom{n}{i} i^k}$ を ${mod 10^9 +7}$ で求めよ． ( ${1\leq n \leq 10^9, 1\leq k \leq 5000}$ )

editorial解法

$f(n,k)= \sum_{i=1}^n \binom{n}{i} i^k$ とする．ここで

$\displaystyle(1+x)^{n} = \sum_{i=1}^{n} \binom{n}{i} x^{i}\$

が成立している．両辺を ${x}$ で微分して ${x}$ をかけると

$x\left(\frac{d}{dx}(1+x)^n\right) = \sum_{i=1}^n \binom{n}{i} i x^{i}$ .

両辺を ${x}$ で微分して ${x}$ をかける操作をさらに ${k-1}$ 回繰り返すと

$x\left(\frac{d}{dx}\cdots x\left(\frac{d}{dx}(1+x)^n\right)\right) = \sum_{i=1}^n \binom{n}{i} i^k x^{i}$ .

右辺で ${x=1}$ とした値は ${f(n,k)}$ なので，左辺を評価して ${x=1}$ とすれば ${f(n,k)}$ を求められる．操作を ${a}$ 回行った時の ${x^{b}(1+x)^{n-b}}~~(0\leq b \leq k)$ の係数を ${dp[a][b]}$ とすると ${O(k^{2}})$ 時間で計算できる.

codeforcesのコメント欄にあった解法

http://codeforces.com/blog/entry/57761?#comment-414448

$f(n,0)= \sum_{i=1}^n \binom{n}{i} =2^{n}-1$ を利用すれば ${O(k^{2}})$ 時間で計算できる.

他の方法

$\displaystyle f(n,1)= \sum_{i=1}^{n} \binom{n}{i} i =n \sum_{i=1}^{n} \binom{n-1}{i-1} = n 2^{n-1}$ ．

また，

整理すると

$f(n,k)= \frac{1}{2}\left( nf(n,k-1) -\sum_{d=1}^{k-1}(-1)^{k-d}\binom{k-1}{d-1}f(n,d) \right)$ .

これらを利用すると $f(n,k)$ を ${O(k^{2}})$ 時間で計算できる.

note

codeforcesのコメント欄にあった解法が強い．