日记 - 伊埃斯的博客站

为了什么？

小红帽的回文数↗

神秘根号分治。

考虑对于 $> \sqrt{n}$ 的 $base$ ，它就只能是两位数。所以我们暴力处理 $\le \sqrt{n}$ 的 $base$ ，对于 $> \sqrt{n}$ 的 $base$ ，我们设它是 $\overline{xy}$ 。显然有 $x = y$ 。所以有 $x \times base + x = x(base + 1) = n$ ，我们直接枚举 $n$ 的因数就是了。

时间复杂度 $O(n \sqrt{n})$ 。

树的计数↗

没学过 Prufer 序列。

题解里说度数为 $d_i$ 的点会在 Prufer 序列里出现 $d_i - 1$ 次，而 Prufer 序列长度为 $n - 2$ ，所以有答案： $ans = \prod_{i = 1}^{n}\binom{sum}{d_i - 1}$ 。 $sum$ 在每次乘完之后都得减掉 $d_i - 1$ 。

排列计数↗

神秘 lucas。

我们发现这玩意形如一个线段树。所以直接预处理出每个点的 $siz_i$ 表示 $i$ 的子树大小。设 $dp_i$ 表示 $i$ 子树内的答案，所以有 $dp_{i} = \binom{siz_i}{siz_{ls}} \times dp_{ls} \times dp_{rs}$ 。

但是要注意的是 $n$ 可能 $\ge mod$ ，所以 init 时预处理到 $\min(n,mod - 1)$ ，组合数要用 lucas 定理算。

好吃的题目↗

必吃的题目。

考虑（我也不知道怎么考虑上的）分治。对于 $R \le mid$ 和 $L > mid$ 可以递归的处理，我们只需要处理 $L \le mid \land R > mid$ 的询问就行。

我们设 $dp_{i,j}$ 在 $i \le mid$ 时表示 $[i,mid]$ 这个后缀的背包，在 $i > mid$ 时表示 $[mid + 1,r]$ 这个前缀的答案。每一层都 $O(nT)$ 的暴力处理。查询时枚举 $x$ ，有 $ans_i = \max_{x = 0}^{T}dp_{L,x} + dp_{R,T - x}$ 。

时间复杂度 $O(nT \log n + qT \log n)$ 。

后日谈

为了真理。

Thanks for reading!

日记

周一 10月 20 2025

427 字 · 2 分钟

life 日记