$ABC\ 132F$
$Description$
给出 $n, k$ ,求由正整数组成的长度为 $k$ 的序列的个数,并使任意两个相邻元素的乘积最多为 $<= n$ ,答案对 $10 ^ 9 + 7$ 取模。
$Solution$
首先很容易看出与除法分块相关。
$yy$ 一下发现第二层答案就是 $\sum_{i = 1}^{n}\left\lfloor\dfrac{n}{i}\right\rfloor$ ,然后后面的答案要根据这个拓展出去。
设 $f_{i, j}$ 表示做到第 $i$ 层,第 $i$ 层做到第 $j$ 个块的答案。
转移从 $f_{i, j - 1}$ 继承,然后考虑第 $j$ 个块元素答案均为 $\left\lfloor\dfrac{l}{n}\right\rfloor$ ,考虑这个块的元素的贡献就是 $\left\lfloor\dfrac{n}{n/l} \times (r - l + 1)\right\rfloor$ ,就有转移方程
$$
f_{i, j} = f_{i, j - 1} + f_{i - 1, cnt - j + 1} \times (r_j - l_j + 1)
$$
初始化 $f_{1, i} = r_i$ 表示起始答案就是到这个块的最大能取的元素个数,直接转移即可。
$Code:$
1 |
|