转眼之间已经到了大三,距退役已经三年了。考完期末考试,正好有一场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)$ 如下:

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

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

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

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

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

换句话说,即求长度为 $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$ 的非负非降序列的方案数。用隔板法可以知道方案数为

那么

至此,只要用筛法预处理出最小质因子,即可在 $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_r$ 的式子得到

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

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

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