CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020-ccpc-online [2020/09/24 16:28]
admin [1001. Art Class]
+++ 2020-2021:teams:intrepidsword:2020-ccpc-online [2020/09/25 23:31] (当前版本)
admin add 1009
@@ 行 22: / 行 22: @@
 时间复杂度 $\mathcal{O}(n\log n)$。
+===== 1002. Graph Theory Class =====
+**题目大意**：有 $2$ 到 $n+1$ 共 $n$ 个点，点 $u$ 和点 $v$ 之间有一条权为 $\text{lcm}(u,v)$。求最小生成树。
+**题解**：每个点都选最小的邻边，如果能连通显然代价最小。对于所有的合数，将它连到一个因子即可；大于 $2$ 的质数则连到 $2$。答案即为 $\left(\sum_{i=2}^{n+1}i\right)+\left(\sum_{i=3,i\text{ is prime}}^{n+1}i\right)$。$\text{min_25}$ 筛即可。
+===== 1007. CCPC Training Class =====
+签到题。
+===== 1009. Math Class =====
+**题目大意**：在模质数 $p$ 的意义下给出 $f(0),f(1),\cdots,f(n)$，求插值后的多项式。
+**题解**：不妨设我们能够求出 $f(1),\cdots,f(p-1)$ 的值，那么相当于我们知道了 $f(\omega^{0}),\cdots,f(\omega^{p-2})$ 的值，而我们需要求出多项式的系数。我们可以惊喜地发现，这就是 IDFT。虽然长度不是 $2$ 的幂，但是有 Bluestein 算法帮我们解决这个问题：
+$$
+\begin{aligned}
+a_{i}&=\frac{1}{p-1}\sum_{j=0}^{p-2}\omega^{-ij}b_{j}\\
+&=\frac{1}{p-1}\sum_{j=0}^{p-2}\text{pow}\left(\omega, -{i+j\choose2}+{i\choose2}+{j\choose2}\right)b_{j}\\
+&=\frac{1}{p-1}\omega^{{i\choose2}}\sum_{j=0}^{p-2}\omega^{-{i+j\choose2}}\omega^{{j\choose2}}b_{j}
+\end{aligned}
+$$
+这样就化为了卷积。
+要求 $f(n+1),\cdots,f(p-1)$ 的值，考虑拉格朗日插值：
+$$
+\begin{aligned}
+f(t)&=\sum_{i=0}^{n}y_{i}\prod_{j=0,j\neq i}^{n}\frac{t-j}{i-j}\\
+&=\sum_{i=0}^{n}\frac{t!y_{i}}{(t-n-1)!(t-i)}\cdot\frac{(-1)^{n-i}}{i!(n-i)!}\\
+&=\frac{t!}{(t-n-1)!}\cdot\sum_{i=0}^{n}\frac{(-1)^{n-i}y_{i}}{i!(n-i)!(t-i)}
+\end{aligned}
+$$
+同样可以用一个卷积完成。
+===== 1012. Xor =====
+**题目大意**：给出 $A,B,K,W$，求 $0\le X\le A,0\le Y\le B,X\oplus Y\le W,|X-Y|\le K$ 的方案数。
+**题解**：唯一的难点在于 $|X-Y|\le K$。不妨设 $X<Y$，考虑 $X,Y$ 第一处不相等的位之后，若 $Y$ 的第 $i$ 位为 $j$，那么给 $Y-X$ 贡献 $j\times2^{i}$；若 $X$ 的第 $i$ 位为 $j$，那么给 $Y-X$ 贡献 $(1-j)\times2^{i}$。也就是说，我们成功使得 $Y-X$ 按位独立了。但是 $Y-X$ 可能在某一位等于 $2$，因此对于 $K$ 不能只记录一位的信息。大致可以证明当前位剩 $4$ 个以上时必然有解，因此数量可以和 $4$ 取 $\min$。

CVBB ACM Team

用户工具

站点工具

页面工具