[Code+#4] 组合数问题2
题目描述
众所周知,小葱同学擅长计算,尤其擅长计算组合数,所以小葱给了你两个数 $n$ 和 $k$,希望你找到 $k$ 个不同的组合数使得这 $k$ 个组合数的和最大。所谓不同的组合数,即对于组合数 $C_{a_1}^{b_1}$ 和 $C_{a_2}^{b_2}$,若 $a_1\neq a_2$ 或者 $b_1\neq b_2$,则我们认为这两个组合数是不同的。现在小葱希望你找到这样 $k$ 个不同的组合数,使得它们互不相同且对于其中任何一个组合数 $C_a^b$ 有 $0\leq b\leq a\leq n$。问这 $k$ 个组合数的和最大是多少?
输入输出格式
输入格式
从标准输入读入数据。
第一行两个整数 $n,k$。
输出格式
输出到标准输出。
一行一个整数,代表 $k$ 个组合数的和对 $10^9+7$ 取模之后的结果;数据保证一定有至少 $k$ 个数可以选。
输入输出样例
输入样例 #1
2 3
输出样例 #1
4
说明
对于 $20\%$ 的数据,$n\leq 10$。
对于 $40\%$ 的数据,$n\leq 500$。
对于另外 $20\%$ 的数据,$k=1$。
对于 $100\%$ 的数据,$1\leq n\leq 10^6,1\leq k\leq 10^5.$
Credit: https://www.luogu.org/discuss/show/38908