【UNR1】合唱队形

Source and Judge

UNR1
uoj214

Record

2h

Analysis

请先思考后再展开

不妨先考虑,n=m的时候如何简便地求出期望
设总课程为A,需要的课程为B, $E=\sum_{i=0}^{B-1} \frac{A}{B-i}$
那么预处理一下g1(B)

然后现在碰到第一个合法的序列就停止,但很难求,不难联想到min-max容斥
然后max也非常好求,用二进制表示起点,直接套用上面的式子即可,时间复杂度为 $2^{n-m}(n-m)m$

考虑m比较小的时候怎么做
因为g1只和B有关,明显可以设一个dp统计每种B的系数
设 $dp(i,S,tot)$ 表示前面的B=tot,然后现在在考虑第i位,
然后用一个S表示前面的起点选择情况,用来辅助判断这次如果选,新产生的课程数量
然后这个可以预处理一个g2(i,S)表示第i位选,i-m+1~i-1的选择情况下,新产生的课程数量
然后对于每个二进制,在最后一个1出现的时候统计答案即可
复杂度为 $O(26n^22^m+nm^2 2^m)$ (大概吧……)

那么对数据分治一下即可

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