转眼之间已经到了大三，距退役已经三年了。考完期末考试，正好有一场 CF，抱着做康复训练的心态参加了比赛。

结果自然是惨不忍睹……虽然是和同学开黑，却也无济于事。写了5道题，最后只过了两道。大概已经不适合快节奏地写代码了吧。

但不管怎么说，这次的题目还是挺有意思的。而且我们的做法和官方做法有些差别，自认为也是很有意思的思路。

A

没啥好说的。把计数的数组开成了 char，贡献了一次 WA。

B

经典题。以各种不同的方式犯傻，一共错了3次。

C

大意是，问有多少个双射 $f$ ，满足对于每个多重集 $S_i$ ， $S_i=f(S_i)$ 。

其实就是对于一种元素 $x$ ，在每个多重集中，其出现次数应当等于 $f(x)$ 的出现次数。可以依次把元素划分成若干等价类，答案即等价类大小的阶乘的乘积。

问题在于如何求出等价类。我们思考了各种方法，最后猜测，说不定是一个看上去很暴力，但其实复杂度可以接受的方法。于是就有了下面这个方法：

用一个 vector<pair<int, int>> 描述元素 $x$ ：每个二元组 $(i,k)$ 代表 $S_i$ 中 $x$ 出现了 $k$ 次，如果 $k=0$ 那么不把这个二元组加入 vector。这样一来所有元素的 vector 长度之和是 $O(\sum{g_i})$ 的。之后要做的就是统计有多少不同的 vector 了。最直观的方法是排序之后扫描，实际上直接对这些 vector 进行排序复杂度也是可以接受的，但考场上没有想明白，就用了哈希的方法。有意思的是，第一次提交只使用了单关键字，之后惨遭 Hack……被迫改成了双关键字。

然而最后数组开小了 RE 了……

最后证明一下排序的复杂度，其实是 $O(n\log n\cdot d)$ ，其中 $d$ 为 vector 的期望长度。这个长度其实是 $O(\sum g_i/n)$ ，所以复杂度就是 $O\left((\sum g_i)\log n\right)$ 。

D

最后只剩15分钟的时候才开始想这题，还是没能在比赛结束前通过。

其实很简单，因为 $n\leq 75$ ，算一算就知道合法分割里最大的数不超过20。因此可以直接状压 DP，状态 $f[i][S]$ 表示前 $i$ 个01，出现数字集合为 $S$ 时的方案数，状态空间 $O(n\cdot2^{20})$ 。而至于转移，两个切割点之间的部分，除去前导零之后长度必然不超过6，而全部为0时不转移；故转移是 $O(1)$ 的。

E

这题非常有意思。

定义 $f_r(n)$ 如下：

\[\begin{align*} f_0(n) & = \sum_{u\cdot v=n}\left[\gcd(u,v)=1\right] \\ f_{r+1}(n) & = \sum_{u\cdot v=n}\frac{f_r(u)+f_r(v)}{2} \end{align*}\]

有 $q$ 个询问，每次给定 $r$ 和 $n$ ，求 $f_r(n)$ 。所有范围均为 $10^6$ 。

可以发现，记 $k$ 为 $n$ 的质因子个数，那么 $f_0(n)=2^k$ 。这是因为每个质因子要么全部属于 $u$ ，要么全部属于 $v$ 。

而 $f_{r+1}$ 的式子可以改写如下：

\[f_{r+1}(n) = \sum_{d\mid n}f_r(d) = \sum_{d\mid n}f_r(d)\cdot 1\]

记 $1(n)$ 为常数函数 $1(n)=1$ ，那么可以将上式表示为 Dirichlet 卷积的形式：

\[f_{r+1}=f_r\ast 1=f_0*1^r\]

和一般卷积一样，Dirichlet 卷积也满足结合律。因此我们研究 $1^r$ 的表达式。

\[\begin{align*} 1^2(n) & = (1 \ast 1)(n) \\ & = \sum_{d\mid n}1\cdot 1 \\ 1^3(n) & = (1^2 \ast 1)(n) \\ & = \sum_{d_2\mid n}\left(\sum_{d_1\mid d_2}1\cdot 1\right)\cdot 1 \\ & \cdots \\ 1^r(n) & = \sum_{d_1\mid d_2\mid \cdots\mid d_{r-1}\mid n}1 \end{align*}\]

换句话说，即求长度为 $r-1$ 的序列 $d_1,\ldots,d_{r-1}$ 的方案数，其中序列满足 $d_i\mid d_{i+1}$ ， $d_{r-1}\mid n$ 。

记 $n$ 的质因数分解为 $n=\prod p_i^{k_i}$ ，仅考虑一个质因子 $p_i$ ，那么 $d_1,\ldots,d_{r-1}$ 的每个数所包含的 $p_i$ 的次数都不应大于 $k_i$ ，且前一个数的次数不应大于后一个数的次数。问题就变成了：求长度为 $r-1$ 且最大数不超过 $k_i$ 的非负非降序列的方案数。用隔板法可以知道方案数为

\[\binom{k_i+r-1}{r-1}\]

那么

\[1^r(n)=\prod_i \binom{k_i+r-1}{r-1}\] \[f_{r}(n) = (f_0 \ast 1^{r-1})(n) = \sum_{d\mid n}f_0(d)\cdot 1^{r-1}\left(\frac{n}{d}\right)\]

至此，只要用筛法预处理出最小质因子，即可在 $O(\tau(n))$ （因子数）的时间内回答一个询问。但这还不够快（比赛时交的这个做法，TLE 在了 Final Test 的第52个点……）。

由于 $d$ 和 $\frac{n}{d}$ 都是 $n$ 的因子，记 $d$ 的质因数分解为 $d=\prod{p_i^{q_i}}$ ，那么 $q_i\leq k_i$ ，而且 $\frac{n}{d}=\prod{p_i^{k_i-q_i}}$ 。进而我们可以将 $f_0(d)$ 表示如下：

\[f_0(d) = \prod_i (1+[q_i>0])\]

带入 $f_r$ 的式子得到

\[\begin{align*} f_r(n) & = \sum_{d\mid n}\left(\prod_i (1+[q_i>0])\right)\left(\prod_i \binom{k_i-q_i+r-1}{r-1}\right) \\ & = \sum_{d\mid n}\prod_i (1+[q_i>0])\binom{k_i-q_i+r-1}{r-1} \\ & = \prod_i\sum_{q_i=0}^{k_i} (1+[q_i>0])\binom{k_i-q_i+r-1}{r-1} \end{align*}\]

因此只要对每个质因子单独计算就可以了。复杂度骤降为 $O(\log n)$ 。

发现了什么吗=·=这个函数是一个积性函数……如果一开始就意识到这一点的话，整个推导其实非常简单，根本不需要考虑什么 Dirichlet 卷积的结合性……

虽然绕了很大的弯路，但这个思路还是挺有趣的😂