[ARC111-C] Too Heavy

首先判断无解：

\[\exists i \in [1, N], p_i \ne i \text{且} b_{p_i} \ge a_i \Leftrightarrow \text{无解} \]

接下来用 \(p_i\) 建个图 \(\forall i \in [1, N], i \rightarrow p_i\) 。

对于某个联通块 \(C\) ，一定是一个环，以任何一个 \(a\) 最大的节点作为起始节点，得到一个便利序列 \(l~(|l| = |V_C|)\)，可以构造方案：

\[\begin{aligned} &l_1 \leftrightarrow l_2\\ &l_1 \leftrightarrow l_3\\ &\cdots\\ &l_1 \leftrightarrow l_n \end{aligned} \]

然后所有联通块的方案拼起来就行了。

[ARC114-C] Sequence Scores

考虑对于一个确定的序列 \(A\) 怎么求出 \(f(A)\) 值。

对于值 \(x\) ，设其在序列 \(A\) 的出现位置序列为 \(l_A(x)\) ，位置从小到大排，特别的 \(l_A(x)_0=0\)。其对 \(f(A)\) 的贡献显然可以这样求：

考虑向一个序列 \(A\) 的末尾添入一个值，变为 \(A'\)，假设当前需要添入 \(x\) ，分情况讨论：

序列 \(A\) 没有 \(x\) ，那么 \(f(A') := f(A) + 1\)
序列 \(A\) 中最后一个 \(x\) 个位置为 \(p\) 则 \(f(A') := f(A) + \left[\min_{i = p + 1} ^ {|A|}\{A_i\} < x\right]\)

设 \(f(n)\) 表示所有长度为 \(n\) 的序列的得分和，\(g(n, x)\) 表示长度为 \(n\) ，最后一个值为 \(x\) 之后的位置的值都大于 \(x\) 的序列个数。

那么可以得到：

\[\begin{aligned} &g(n,x)=\sum_{i=1}^n m^{i-1} (m-x)^{n-i}\\ &f(n)=\sum_{i=1}^m f(n-1)+m^{n-1} - g(n-1,i) \end{aligned} \]

考虑一个连通图 \(C\) 的答案。

如果 \(K\) 是奇数，那么 \(\rm{ANS}\) 必然为 \(0\) ，只用考虑 \(2 \mid K\) 的情况。

首先想一棵树的情况：考虑确定所有节点的度数奇偶性，从叶子结点开始向上确定每一条边是否选择，可以发现选择方案是确定的，因此对于一棵树而言：

\[\mathrm{ANS}_K=\binom{|V_C|}{K} \]

接下来考虑一般情况，首先随便弄一棵生成树，然后对于非树边，随便选择一些，然后再确定节点的度数奇偶性，发现对于树边，其选择方案一定是确定的，因此有：

\[\mathrm{ANS}_K=\binom{|V_C|}{K} 2^{|E_C|-|V_C|+1} \]

对于所有联通块，用背包对答案进行合并，合并方法可以用类似树形背包的方法，可以做到 \(O(n^2)\) 。