Codeforces Round 1049 (Div. 2) 部分题解
D. A Cruel Segment's Thesis
可以发现最后是选 \(\lfloor\frac{n}{2}\rfloor\) 对区间，一半取 \(r\) 一半取 \(l\) 配对相加。
那可以假定所有区间选 \(r\) 再选出 \(l+r\) 最优的一半区间合进去就可以了。
在 \(n\) 是奇数时，需要删掉一个区间不计入答案，我们枚举删除的区间是哪个，统计删除后的答案是容易的。
E. Prime Gaming
E1 可以用 dp，\(f_{n,s,0/1}\) 表示现在剩 \(n\) 个状态为 \(s\) 先后手走最终的剩余是什么。
现在考虑 E2，先考虑怎么确定一个序列的最终答案，考虑枚举这个答案，将小于其的设 \(0\) 大于等于的设 \(1\) ，若这个状态答案为 \(1\) 则答案大于等于这个值。
E2 可以枚举答案 \(k\) ，将序列大于等于 \(k\) 的设 \(1\) 小于 \(k\) 的设 \(0\) 就又转化成了 E1 的问题，于是可以统计出来最终答案大于等于 \(k\) 的序列个数，差分一下就是恰好等于 \(k\) 的序列个数，就可以相加了，复杂度 \(O(n2^n+nm)\)。
bonus，求对于 \(m \leq 10^9\) ，每个数互不相同的答案。
求出 \(cnt[s]\) 表示多少个二进制序列最终答案为 \(1\)，答案为：
\[\sum_{i=1}^m\sum_{r=1}^n \binom{i-1}{n-r}\binom{m-i+1}{r}cnt[r]\cdot r!(n-r)!
\]
转化一下：
\[=\sum_{r=1}^n cnt[r]r!(n-r)!\sum_{i=1}^m\binom{i-1}{n-r}\binom{m-i+1}{r}
\]
第二个和式的组合意义为：将 \(m\) 个数划分，左边选 \(n-r\) 个右边选 \(r\) 个，等价于 \(m\) 个数选 \(n-r+r\) 个，这个划分不完整（\(i=m\) 时不是全部左划分），去掉一种情况（其实这个边界答案就是 \(0\)），化简为：\(\binom{m}{n}\)，得到答案：
\[=\sum_{r=1}^ncnt[r]r!(n-r)!\binom{m}{n}
\]