AtCoder Regular Contest 104
A Plus Minus
普及题，解方程。
B DNA Sequence
枚举区间前缀和判断合法即可。
C Fair Elevator
先排除出现重复或 \(L\ge R\) 的明显不合法情况。
观察发现一个合法的最终情况应当形如：\((1,4),(2,5),(3,6),(7,9),(8,10)\)，也就是分成多个长度为偶数的区间，且每个区间内有对应数对 \((i,i+L)\)，即左端点均在左侧右端点均在右侧，而每个数对值相等，为区间长度一半。
两个不同区间独立，可以用 DP 去判断合法的划分，假设 \(dp_j=1\)，现在判断 \([j+1,i]\) 能否被划分。
实际上就是看填成上面的结果是否合法，具体判断：
-
左侧区间位置全部没有出现或作为左端点出现，右侧区间位置全部没有出现或作为右端点出现。
-
左侧区间作为左端点出现的位置 \(k\)，当且仅当 \((k,k+L)\) 是一确定信息或 \(k+L\) 没有出现。
-
右侧区间作为右端点出现的位置 \(k\)，当且仅当 \((k-L,k)\) 是一确定信息或 \(k-L\) 没有出现。
时间复杂度 \(O(n^3)\)。
D Multiset Mean
平均数为 \(x\) 可以写作 \(\sum_{i=1}^{cnt} s_i=cnt\times x\)，发现其中有 \(cnt\) 和 \(\sum\) 两个需要维护的，不太好统计。
考虑把式子修改一下，\(x\) 自然是随便选，所以只考虑不为 \(x\) 的选取方案。移项一下：\(\sum_{i=1}^{cnt} s_i-x=0\)，按正负划分可以得到：\(\sum_{s_i<x} x-s_i=\sum_{s_i>x} s_i-x\)。本质是左侧值域为 \([1,x-1]\)，右侧值域为 \([1,n-x]\)，选取个数任意要求和相等。
转化成一个看起来简单一点的问题：求 \(f_{i,j}\) 表示值域 \([1,i]\)，可选取 \([0,k]\) 个且和为 \(j\) 的方案数，容易写出转移方程：
貌似是和模 \(i\) 的值有关的，类似于维护一个队列，每次加入当前的 \(f_{i-1}\) 值，如果队列元素超过 \(k+1\) 个就弹出队首，答案就是当前队列的元素和。
时间复杂度 \(O(n^4)\)。
多重集 \([0,k]\) 的选取可以写成生成函数的形式 \(\prod_{j} F_j(x)\)，其中 \(F_j(x)=\sum_{i=0}^k x^{ij}\)，但好像并不会简化问题。
E Random LIS *
神仙题。
LIS 本质是关于离散化后的数组求出的。
可以 \(O(n^n)\) 枚举这样的偏序关系，去掉不合法的状态。
设 \(b_i\) 为离散化后值为 \(i\) 的所有位置的最小 \(a\) 值，取后缀 \(\min\) 后就得到实际合法值域。
题目转化成了 \(x_i\in [1,b_i]\)，要求 \(x_i\) 单调递增。
开始想到一个类似于分段函数维护特殊点值来优化 DP 的做法，实际比较复杂。
题解做法比较优秀，实际上不方便处理的就是不同的 \(x_i\) 会使得 \(x_{i+1}\) 的实际取值范围不同，但上界是一定的，而固定值域 \((b_i,b_{i+1}]\) 中选取 \(k\) 个数的方案本身是“钦定有序”的，既然实际取值范围会不同，不妨枚举出每个值具体落在哪一段，段内的方案数可以组合数求出。
设 \(f_{i,j}\) 为前 \(i\) 段选取了 \(j\) 个数的方案数，其中第 \(i\) 段为 \((b_{i-1},b_i]\)，则转移：
暴力求组合数，单次 DP 是 \(O(n^4)\) 的，可以通过。