UNR 2 题解

积劳成疾

最大值这种东西的 dp，考虑删去最大值的类笛卡尔树思想。

$f[i, j]$ 表示长度为 $i$ 的区间，最大值不超过 $j$ 的价值和

$f[i, j] = f[i, j - 1] + \sum\limits_{k = 1}^{i} f[k - 1, j] * f[i - k][j - 1] * w[j]^{跨过 k 的区间个数}$

$Code$

梦中的题面

数位 dp？感觉巨大麻烦

先不管大数，考虑经典容斥：

$$ans = \sum\limits_{S = 0}^{2^m - 1} (-1)^{|S|} \binom{n + c * |S| - |S| - \sum\limits_{i \in S} b^i + m}{m}$$

接下来都设 $n$ 表示原来的 $n + c * |S| - |S|$

设 $n’ = n - \sum\limits_{i \in S} b^i$

枚举 $|S|$，把 $n$ 算出来。

大组合数不好搞。

注意到 $\binom{n’ + m}{m}$ 是个关于 $n’$ 的 $m$ 次多项式，我们可以算出所有个数为 $|S|$ 的 $n’$ 的 $k$ 次方和，系数预处理即可。

$dp[i, j, k]$ 表示前 $i$ 个选了 $j$ 个位置的 $k$ 次方和。

**直接把 $n$ 拼进去没法保证 $n’ \geq 0$**。呜呜。

所以还要枚举 $\sum\limits_{i \in S} b^i$ 是从哪位开始小于 $n$ 的，后面的就可以任选了。有救就好。等于的情况判一下。

那就要先转 $b$ 进制了。麻烦。

$O(m^4)$。

upd：细节一大堆！！大概是我最近最刚的一次。调大半天了，孩子傻了谢谢。AC 了，感动。长是长了点，但是跑的贼特喵快！！哼这是胜利。

细节有在代码里注明。

$Code$

本题 $c \in {0, 1}$，有做法是分 $0$、$1$ 讨论的（$c = 1$ 时分位讨论，数位 dp；$c = 0$ 时再加一维表示之前 $x_i = b^i$ 的个数），相比之下好像细节也不少…… QAQ 然而完全可以拓展到 $c \leq M$ 嘛。