526互联

2024.1 杂题

发布时间 2024-01-05 11:37:34作者: cnyz

To be a rock and not to roll.
这篇文章，以及以后可能的一些文章，会把同一个来源的题丢一块。

目录

牛客挑战赛 72 C. Crying 与哈密顿路

Tag：D-树形 DP；D-背包。
令 \(f_{u,i}\) 表示 \(u\) 子树内的节点连出 \(i\) 条子哈密尔顿路的最优解，转移类似树形背包。
即 \(f_{u,i}+f_{v,j}+ka_u\to f'_{u,i+j-k}\)，其中对于 \(k\) 的枚举有上界 \(2\min(i,j)\)，对应将对应的若干条哈密尔顿路首尾相接。
总复杂度 \(O(n^3)\)，Code。

D. Crying 与 404

Tag：S-主席树。
因为是排列，所以 \([l,r]\) 内没有的数，就是 \([1,l-1]\cup [r+1,n]\) 里有的数。
使用主席树求第 \(k\) 大即可，注意要特判 \(k\ge r-l+1\) 的情况，\(O(n\log n)\)，Code。

E. Crying 与初中数学

Tag：M-整除分块；M-莫比乌斯反演；M-杜教筛；M-线性筛。
尝试枚举 \(a,b\)，即求：

\[\sum_{a=1}^{\sqrt{N}}\sum_{b=1}^{N/a^2} \mu^2(b)(a+b) \]

可以结合 \(\mu\) 的定义得到上述式子，套路展开成：

\[\sum_{a=1}^{\sqrt{N}}a\sum_{b=1}^{N/a^2} \mu^2(b)+\sum_{a=1}^{\sqrt{N}}\sum_{b=1}^{N/a^2}\mu^2(b)b \]

首先对于所有的 \(a\)，\(N/a^2\) 的个数是有限的，大致是 \(O(N^{1/3})\) 量级。
有经典结论：

\[\mu^2(i)=\sum_{d^2|i} \mu(d) \]

可导出：

\[\begin{aligned} \sum_{i=1}^{N}\mu^2(i)&=\sum_{i=1}^{\sqrt{N}} \mu(i)\lfloor\frac{N}{i^2}\rfloor\\ \sum_{i=1}^N\mu^2(i)i&=\sum_{i=1}^{\sqrt{N}}\mu(i)i^2\lfloor\frac{N}{i^2}\rfloor \end{aligned} \]

对外层按 \(N/a^2\) 分段，内层则同样是类似的分段方式，剩下的就是求 \(\sum \mu(i)\) 和 \(\sum \mu(i)i^2\)，两者均可以用杜教筛带走。
需要设置合理的预处理范围，出题人题解说复杂度是 \(O(N^{3/7})\) 的，但是我不会证，Code。
感觉这类的数论题大部分都需要整预处理来平衡复杂度，很厉害。

2nd Ucup Stage 16 A. Bracket-and-bar Sequences

Tag：D-计数 DP。
写个暴力会发现合法的括号序列个数比 \(2\times 10^{18}\) 要小，所以直接按照一定顺序编号即可，有点细节但不多。
然后写暴力试填即可，Code。

C. Find the Parts

Tag：H-构造；H-哈希；cin 的使用方法。
发现我们可以用的 bit 数量大约是矩阵的 \(\frac{1}{10}\)，直接对着这个想。
发现存下来第 \(10n\) 行就行了，这样一定可以存下来查询矩阵的某一些东西，然后就可以跑哈希直接找到这个矩阵里面的某一行了。
复杂度没算，但是好像有点慢，不管了能过，Code。

JOISC 2020 Day4 Capital City

Tag：H-贪心；T-点分治。
有贪心：任取某个点为根，现在试图将这个根到与其同颜色的点打通，则枚举每一个同颜色的点向上跳父亲直到跳到同颜色即可，注意可能中途会加入其它节点。
有性质：如果在某一方案中染色到了 \(x\)，则从 \(x\) 出发的染色方案一定不劣于当前的方案，证明：显然有上界次数为直接把这个方案拿过来用。
使用点分治来加速贪心的过程，每次贪心的时候发现贪心的部分越出了子树就跳出不做，即可做到 \(O(n\log n)\)，Code。

LOJ6485 LJJ 学二项式定理

Tag：M-单位根反演。
单位根反演即：\([n|a]=\frac{1}{n}\sum_{k=0}^{n-1}\omega_n^{ak}\)。
可以导出 \([a\bmod p=b]=[p|(a-b)]=\frac{1}{p}\sum_{i=0}^{n-1}\omega_n^{ai}\omega_n^{-bi}\) 这样的式子。
对于原题，施单位根反演得：

\[\begin{aligned} &\sum_{i=0}^n \binom n i s^i \sum_{j=0}^3 [i\bmod 4=j]a_j\\ =&\sum_{i=0}^n \binom n i s^i \sum_{j=0}^3 a_j\sum_{k=0}^3 \omega_4^{ki}\omega_{4}^{-kj}\\ =&\sum_{j=0}^3 a_j \sum_{k=0}^3 \omega_4^{-kj}\sum_{i=0}^n \binom n i s^i\omega_4^{ki}\\ =&\sum_{j=0}^3 a_j \sum_{k=0}^3 \omega_4^{-kj}(s\omega_4^k+1)^n \end{aligned} \]

在 \(\bmod 998244353\) 意义下计算 \(\omega_4\) 是简单的，Code。

洛谷 P5591 小猪佩奇学数学

Tag：M-单位根反演。
可以将 \(\lfloor\frac i k\rfloor\) 拆成 \(\frac 1 k (i-(i\bmod k))\)，则有：

\[\begin{aligned} & \sum_{i=0}^n \binom n i p^i \lfloor\frac i k\rfloor\\ =& \frac 1 k(\sum_{i=0}^n\binom n i p^ii-\sum_{i=0}^n\binom n i p^i(i\bmod k))\\ \end{aligned} \]

先只看左侧，可以将 \(i\) 置换进组合数，可以得到：

\[\begin{aligned} &\sum_{i=0}^n\binom n i ip^i\\ =&np\sum_{i=0}^n\binom {n-1} {i-1} p^{i-1}\\ =&np(p+1)^{n-1} \end{aligned} \]

可以 \(O(\log n)\) 的解决，考虑右边，枚举 \(i\bmod k\) 有：

\[\begin{aligned} &\sum_{i=0}^n\binom n i p^i(i\bmod k))\\ =&\sum_{i=0}^n\binom n i p^i \sum_{j=0}^k j[k|(i-j)]\\ =&\frac 1 k\sum_{i=0}^n\binom n i p^i\sum_{j=0}^{k-1}j\sum_{l=0}^{k-1}\omega_{k}^{il}\omega_k^{-jl}\\ =&\frac 1 k\sum_{l=0}^{k-1}\sum_{j=0}^{k-1}j\omega_k^{-jl}\sum_{i=0}^n\binom{n}{i}p^i\omega_k^{il}\\ =&\frac 1 k\sum_{l=0}^{k-1}(p\omega_k^l+1)^n\sum_{j=0}^{k-1}j\omega_k^{-jl}\\ \end{aligned} \]

目前已经导出了一个 \(O(k^2)\) 做法，但是 \(\sum_{j=0}^{k-1}j\omega_k^{-jl}\) 这个形式是错位相减，可以导出 \(O(\log k)\) 的计算式。
下面写一下推导：令 \(S(n,k)\) 表示 \(\sum_{i=0}^{n-1} ik^i\)，有结论，此时的 \(S(n,k)=(An+B)k^n-B\)，其中 \(A,B\) 为参数。
注意到此时 \(k^n=(\omega_k^{-l})^k=1\)，所以 \(S(n,k)=An\)，结合结论有 \(A=\frac{1}{k-1}\)，即 \(S(n,k)=\frac{n}{k-1}\)，注意要特判 \(k=1\)。
做到 \(O(k\log k)\)，done，Code。

ARC161E Not Dyed by Majority (Cubic Graph)

Tag：H-随机化；G-2-SAT。
啊？
结论：答案占比比较大。
随机答案，现在问题转化为写 checker，发现这东西就是一个 2-SAT，限制形如 \(a\) 取了 B 则 \(b,c\) 取 W，这样的，直接建图即可。
Code。