P9035 「KDOI-04」Pont des souvenirs

· · 个人记录

首先如果没有第一个限制，方案数是 n + k - 1\choose n，也就是隔板法。

然后考虑第二个限制。实际上，就是要求 a_{n-1} + a_n \le k + 1。

考虑固定 a_n。这时 a_{n-1} 最多选 \min(a_n, k + 1 - a_{n})。于是方案数用隔板可以算，不写了。

然后我们的组合数有一个性质，即

\sum\limits_{i=l}^r {i\choose k} = {r+1\choose k + 1} - {l\choose k + 1}

我不太会证。。。

然后套下就出来了。比较厉害。