拜谢 zaky！
首先考虑 \(B_i\leq 1\) 的部分分，我们考虑采用一种“提前”的 dp 方法。我们设 \(f_{i,j}\) 表示从后往前考虑到第 \(i\) 个，仍有 \(j\) 个 \(0\) 需要变成 \(1\) 的方案数。每次转移的时候枚举当前这个值最终是什么，并选择 \([i+1,n]\) 中的一个数转移过去。
进一步的，我们可以得到一个普适的 dp：设 \(dp_{i,S}\) 表示从后往前到第 \(i\) 个，\([i+1,n]\) 中序列为 \(S\)，其中 \(S_i\) 表示仍有 \(S_i\) 个 \(i\) 需要被减少到至少 \(0\) 以下。这里需要将至少容斥成恰好，也即如果枚举了 \(x\) 的最终值是 \(C_x(A_x\leq C_x\leq B_x)\)，需要用 \(x\) 最终至少是 \(C_x\) 的方案数减去 \(x\) 最终至少是 \(C_x+1\) 的方案数，这样的复杂度是 \(n\choose B\) 级别的。
这样子并不够优。可以注意到的是，刚开始 \(S\) 内所有数的和是 \(\leq B\) 级别的，如果能让过程中都保持这个状态，那么复杂度就是可以接受的。会使 \(S\) 内所有数变大的情况是某个数顶到了 \(B_x\) 的上界，我们考虑单独处理。我们可以再进行一个容斥，将 \(B_x\) 顶到上界用 \(x\) 随意连减去 \(x\) 不顶到上界的情况。为此，我们重设 dp 状态为 \(dp_{i,j,S}\)，其中 \(j\) 表示后面有 \(j\) 个数是可以随意连的。转移需要分类讨论一下每个数是连向非随意连还是随意连。如果连向非随意连，那么 \(S\) 内数的总和会至少减去 \(A_x\)，否则当前数也可以看作随意连，总和不变。
状态数是 \(O(n^2\pi(B))\) 的，其中 \(\pi(B)\) 表示 \(B\) 的划分数，转移数是 \(B^{1.5}\) 的，预处理划分数之间的转移以后就可以做到 \(O(n^2\pi(B)B^{1.5})\) 。
不要写记搜，慢死了。
标签：随意,转移,26,UR,leq,UOJ,pi,数是,dp From： https://www.cnblogs.com/275307894a/p/17797666.html