lg9035题解
考虑枚举\(a_{n-1}=l\),根据题意\(l\leq a_n\leq k+1-l\),这说明\(a_n\)有\(k+1-2l\)种取值。
令\(b_i=a_i-a_{i-1}\),则\(b_1\geq 1\),\(b_i\geq 0(i>1)\),\(b_1+...+b_{n-1}=l\)
让\(b_{2...n-1}\)都加上\(1\),得到\(b_1+(b_2+1)+...+(b_{n-1}+1)=l+n-2\),\(b_1,b_2+1....b_{n-1}+1\)都>1。使用插板法计算方案为\(C_{l+n-3}^{n-2}\)
当\(l=0\)方案数为\(k+2\),\(l>0\)方案数为\((k+1-2l)C_{l+n-3}^{n-2}\)
我们要计算\(k+2+\sum_{l=1}^{\lfloor \frac{k+1}{2}\rfloor}(k+1-2l)C_{l+n-3}^{n-2}\),时间复杂度\(O(k)\)
考虑优化计算\(\sum_{l=1}^{\lfloor \frac{k+1}{2}\rfloor}(k+1-2l)C_{l+n-3}^{n-2}\),等于计算\((k+1)\sum_{l=1}^{\lfloor \frac{k+1}{2}\rfloor}C_{l+n-3}^{n-2}\)与\(\sum_{l=1}^{\lfloor \frac{k+1}{2}\rfloor}(-2l)C_{l+n-3}^{n-2}\)的和
第一部分事实上等于要求\(\sum_{i=0}^nC_{k+i}^{k}\),这是个经典问题,累加可以得到\(C_{k+n+1}^{k+1}\)。令\(F(k,n)=\sum_{i=0}^nC_{k+i}^{k}=C_{k+n+1}^{k+1}\)
第二部分等于要求\(\sum_{i=0}^nC_{k+i}^{k}(i+1)\),等于计算\((n+2)\sum_{i=0}^nC_{k+i}^k-\sum_{i=0}^nC_{k+i}^k(n+1-i)\),等于计算\((n+2)F(k,n)-F(k,0)-...-F(k,n)=(n+2)F(k,n)-(C_{k+1}^{k+1}+C_{k+2}^{k+1}+....+C_{k+n+1}^{k+1})=(l+2)F(k,n)-F(k+1,n)\),预处理阶乘后可以\(O(1)\)计算。
最新文章
- C#委托(delegate)
- Linux中exec命令相关
- 2015 Multi-University Training Contest 1 - 1009 Annoying problem
- EDIUS分别输出视频和音频的教程
- 百度面试题:从输入url到显示网页,后台发生了什么?
- hdu-5695 Gym Class(贪心+拓扑排序)
- Barracuda VS antelope
- leetcode—word ladder II
- R语言数据分析系列六
- Java——异常谜题
- [BZOJ4518]征途
- requirejs 加载其它js
- Python内置函数(13)——complex
- C#标准体重判断
- 域渗透之通过DCSync获取权限并制作黄金票据
- 常用的node.js模块
- 如何开发mis系统--整理
- oracle in 函数
- spark图解
- C#网络爬虫--多线程处理强化版