P6622 [省选联考 2020 A/B 卷] 信号传递

题目大意

详细题目传送门
给出 \(n,m,k\) 和一个长度为 \(n\) 的序列 \(S\)，其中 \(S_i\in [1,m]\)。
对于一个 \(x\rightarrow y\) 的代价 \(f(x,y)\)，有：

\[ \left\{\begin{aligned}y-x &&x\leq y\\kx+ky &&x>y\\\end{aligned}\right.\]
你需要求一个长度为 \(m\) 排列 \(P\),使 \(\sum_{i=1}^{n-1}f(P_{S_i},P_{S_i+1})\) 最小。
\(n\leq 10^5,m\leq 23,k\leq 100\)
思路

发现 \(m\) 很小，所以看起来就很像一些状压动归。但是发现即使是枚举 \(P\) 的暴力要求一个总代价也是 \(O(n\cdot m!)\) 的，所以希望将它转成一个只关于 \(m\) 的形式。
这个时候可以拆贡献，发现对于 \(S_i\) 的贡献只与 \(S_i+1\) 有关。这个时候我们可以记 \(C(x,y)\) 表示 \(S\) 中有多少 \((S_i=x,S_{i+1}=y)\)。这样我们在算 \(P\) 的代价时就可以枚举 \(x,y\in[1,m]\)，然后加贡献

\[C(x,y)\cdot\left\{\begin{aligned}P_y-P_x &&_x\leq P_y\\kP_x+kP_y &&_x>_y\\\end{aligned}\right.\]
这样就优化到了 \(O(m^2m!)\)，我们的时间复杂度已与 \(n\) 无关。
然后考虑状压动规。如果先考虑 \(F_s\) 表示现在 \([1,|s|]\) 的数分别填在了 \(s\) 为 \(1\) 的位置上，但是无法转移，因为不知道具体是哪些值的话 \(C(x,y)\) 就是无法更新的。
但是可以有转移 \(F_s\) 表示现在填了前 \(|s|\) 个位置，填了 \(s\) 中的这些数。发现就可以转移，因为我们只关心大小关系，那么还没有出现的肯定在之后，那么转移时的大小关系就可以确定了。
那么转移一个 \(i\) 时考虑到 \(j\) 有几种情况：

• 若 \(i\rightarrow j\)， \(j\in s\)，\(P_jP_i\)，所以有贡献 \(C(i,j)\cdot (-P_i)\)
  
• 若 \(j\rightarrow i\)， \(j\in s\)，\(P_jP_i\)，所以有贡献 \(C(j,i)\cdot kP_i\)
  

那么可以转移

\[G(s,i)=\sum_{j\in s}(C(i,j)\cdot k+C(j,i))+\sum_{j\notin s}(-C(i,j)+C(j,i)\cdot k)\]

\[F_{s\cup i}\leftarrow F_s+P_iG(s,i)\]
其中按照定义 \(P_i=|s|+1\)。
那么现在的时间复杂度是 \(O(2^mm^2)\) 的，已经有 \(80\) 分了。发现能不能先预处理出 \(G(s,i)\)。发现 \(G(s,i)\) 可以从任何一个大小为 \(|s|-1\) 的子集转移过来。那么可以不妨从去掉最低位 \(1\)（即 lowbit，不妨设位置为 \(j\)） 的位置 \(s^{'}\) 转移。

\[G(s,i)=G(s^{'},i)+C(i,j)\cdot k+C(j,i)-(-C(i,j)+C(j,i)\cdot k)\]

\[=G(s^{'},i)+C(i,j)\cdot (k+1)+C(j,i)\cdot (1-k)\]
现在我们已经做到了时空都是 \(O(2^mm)\) 了，但是发现空间不够大。但是发现所有的 \(G(s,i),i\in s\) 都是没有意义的，所以我们可以只保存 \(2^{m-1}\) 个 \(G\)，虽然实现麻烦但是可以优化到空间 \(O(2^{m-1}m)\),时间 \(O(2^mm)\) 可以通过本题。
代码

[code]#include#define endl '\n'#define rep(i,a,b) for(register ll i=(a);i