前言

T3挂没了，此记。

A

AT_chokudai_S002_k

考虑建图，发现如果一个联通块存在环就可以全部贡献，否则只能贡献联通块大小 \(-1\)。

直接算就行。

P10116

拆贡献，依次对每个出现的位置的方案进行累加。

发现无论序列出现在哪里，方案数都是一样的，直接算钦定位置后的方案乘上 \(n-m+1\) 即可。

首先留出 \(m\) 次操作给 \(m\) 个位置最后做，剩余操作取值任意，有 \(k^{q-m}\) 种方案。

则我们要求满足条件的操作下标序列的方案数，使得下标 \(1\sim m\) 各至少出现一次。

考虑容斥，钦定 \(i\) 个位置没被选，则方案数为 \(C_{m}^i\times (n-i)^q\)。

故答案为

\[k^{q-m}\times (n-m+1)\times \sum_{i=0}^m (-1)^i C_m^i \times (n-i)^q \]

P8476

设 \(f_{i,j}\) 表示考虑到 \(i\) 位置，\(b_i=j\) 的最小值。

\[f_{i,j}\gets \min_{k\ge j} {f_{i-1,k}+F(j,a_i)} \]

发现最优解下必定 \(\forall i,\exist j,a_j=b_i\)。

记对 \(a\) 排序后的数组为 \(c\)。

于是改变状态，设 \(f_{i,j}\) 表示到 \(i\) 位置，\(b_i=c_j\) 的最小值。

设 \(g_{i,*}\) 表示 \(f_{i,*}\) 的后缀最小值，于是

\[g_{i,j}\gets {g_{i-1,j}+F(c_j,a_i)} \]

考虑从 \(g_{i-1,*}\to g_{i,*}\) 有什么变化。

设 \(c_k=a_i\)。

若 \(j<k\)，则 \(g_{i,j}=g_{i-1,j}+C\)。

否则 \(g_{i,j}=g_{i-1,j}+c_j-c_k\)。

发现前者是区间加，后者是区间减+区间加 \(a_i\)。

发现 \(c_j\) 与 \(g_{i,*}\) 均单调不降，于是 \(g\) 操作后被分成了两段单调不降的序列。

取后缀 \(\min\) 直接二分+区间覆盖。

上述所有操作均可线段树。