题解 P5339 [[TJOI2019]唱,跳,rap和篮球]
在我的博客查看
没学过生成函数,暴力容斥了.
感觉这种在序列上的组合问题会一下子想到容斥.
用 c,t,r,l 分别表示喜欢唱,跳,rap,篮球的同学.
首先,如果要用容斥解决的话,可以从序列中连续的 c,t,r,l 的个数入手.
首先需要计算当 $a,b,c,d$ 都无穷大,即每个位置都可以放 c,t,r,l 中任意一个同学时,长为 $n$ 的序列中有 $m$ 个连续的 c,t,r,l 的方案.
定义 $\mathrm{C}_n^m$ 为长为 $n$ 的序列里选 $m$ 个元素,且被选出的任意两个元素之间距离不小于 $4$,那么上面所提到的方案的计算式