BZOJ 4403 序列统计

发布于 2017-06-14  113 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4403

题意:给定三个正整数 N、L 和 R,统计长度在 1 到 N 之间,元素大小都在 L 到 R 之间的单调不降序列的数量。答案对 1000003 取模


我们考虑数字间的大小关系其实是没有影响的
所以 [l,r] 等价于 [1,m] m=r-l+1
考虑元素数量为 i 时的情形 一个长度为 i 的单调不降序列 元素范围在 [1,m]
设 x_j 为第 j 个元素取了多少个, 显然有\(sum_{j=1}^{m}x_j=i\)
那么就是 n 个球,m 个盒子, 盒子可以为空的方案数...
插板法即可, 处理空盒子可以给每一个盒子加一个元素 即总元素为 i+m 这样满足盒子非空即可
那么此时\(ans=sum_{i=1}^{n}C(i+m-1)(m-1)\)
怎么处理这个式子呢 写出来大概看的清楚些
ans=C(m)(m-1)+C(m+1)(m-1)+C(m+2)(m-1)+...+C(m+n-1)(m-1)
加上一项 C(m)(m), 减去一项 1
由于有:C(m+1)(m)=C(m)(m)+C(m)(m-1) 所以可以依次合并每一项
即 ans=C(n+m)(m)-1
由于模数不大 lucas 即可

 


一个非常弱的准退役OIER