2020-2021:teams:intrepidsword:2020-ccpc-online

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:intrepidsword:2020-ccpc-online [2020/09/24 17:11]
admin update
+++ 2020-2021:teams:intrepidsword:2020-ccpc-online [2020/09/25 23:31] (当前版本)
admin add 1009
@@ 行 32: / 行 32: @@
 签到题。
+===== 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 =====

2020-2021/teams/intrepidsword/2020-ccpc-online.1600938666.txt.gz · 最后更改: 2020/09/24 17:11 由 admin