【jsc2019-qual F】Candy Retribution

Source and Judge

jsc2019-qual F

Analysis

请先思考后再展开

$$
记g(n,m)=将n划分为m个可空段=C_{n+m-1}^{m-1},然后显然我们求solve(R)-solve(L-1) \\
考虑有序下B,注意到 B_m=B_{m+1} 明显没有 B_m \neq B_{m+1} 好做,故容斥 \\
计数的时候用 B_{m+1}来唯一统计序列,枚举B_{m+1}=t \\
然后你发现直接等不好处理,转化成不等号
则方案数为f(t-1,t)-f(t-1,t+1) \\
容斥求f(B_m \leq a,B_{m+1}\geq b)=C_n^m \sum_{i=0}^m (-1)^iC_m^i g(R-i(a+1)-(n-m)b,n+1) \\
n+1的1表示可以丢掉,且注意到i \leq min(m,R/t),复杂度为调和级数 O(RlogR)
$$

code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5056.html
转载请注明出处,谢谢!