ARC104
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\)，发现其中有 \(n\) 和 \(\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\) 的方案数，容易写出转移方程：
\[f_{i,j}=\sum_{l=0}^{\min(k,\left\lfloor j/i\right\rfloor)} f_{i-1,j-l\times i} \]貌似是和模 \(i\) 的值有关的，类似于维护一个队列，每次加入当前的 \(f_{i-1}\) 值，如果队列元素超过 \(k+1\) 个就弹出队首，答案就是当前队列的元素和。
时间复杂度 \(O(n^4)\)。
多重集 \([0,k]\) 的选取可以写成生成函数的形式 \(\prod F_k(x)\)，其中 \(F_k(x)=\sum_{i\ge 0} x^{ki}\)，但好像并不会简化问题。
标签：cnt,乱写,sum,ARC104,合法,端点,区间,106 From： https://www.cnblogs.com/SoyTony/p/Problems_in_ARC_104_to_106.html