多项式

· · 个人记录

设已知

G(F_{\frac{n}{2}}(x)) \equiv 0 \mod x ^ {\frac{n}{2}}

求

G(F_{n}(x))\equiv0\mod x^n G(F_{n}(x)) = \sum_{i=0}^{\inf} \frac{G^i(F_{\frac{n}{2}}(x))*(F_n(x) -F_{\frac{n}{2}}(x))^i}{i!}\mod x^n

显然F_{\frac{n}{2}}(x) \in F_{n}(x)

\sum_{i=2}^{\inf} \frac{G^i(F_{\frac{n}{2}}(x))*(F_n(x) -F_{\frac{n}{2}}(x))^i}{i!} \equiv0\mod x^n

所以

G(F_{n}(x)) \equiv \sum_{i=0}^{1} \frac{G^i(F_{\frac{n}{2}}(x))*(F_n(x) -F_{\frac{n}{2}}(x))^i}{i!}\mod x^n G(F_{n}(x)) \equiv G(F_{\frac{n}{2}}(x))+G^{'}(F_{\frac{n}{2}}(x))*(F_n(x) -F_{\frac{n}{2}}(x))\mod x^n F_n(x) = F_{\frac{n}{2}}(x) - \frac{G(F_{\frac{n}{2}}(x))}{G^{'}(F_{\frac{n}{2}}(x))}

设已知 F(x)*G(x) = 1

显然 f_0*g_0 = 1

设已知 G(x) * F_\frac{n}{2}(x)\equiv0\mod x^{\frac{n}{2}}

F_n(x) - F_\frac{n}{2}(x) \equiv 0 \mod x^{\frac{n}{2}} (F_n(x) - F_\frac{n}{2}(x))^2 \equiv 0 \mod x^{n} F_n(x)^2 - 2 * F_\frac{n}{2}(x) * F_n(x) +F_\frac{n}{2}(x)^2\equiv 0 \mod x^n F_n(x) \equiv 2 * F_\frac{n}{2}(x) -F_\frac{n}{2}(x)^2*G(x) \mod x^n F_0= inv(G_0)

已知F(x),G(x) 求R(x),H(x)

其中F(x) = G(x) * H(x) + R(x)且

G(x)$次数为$n-m$，$R(x)$次数小于$m

已知F(x)=\sum_{i = 0}^na_ix^i

设F^T(x) = \sum_{i = 0}^na_{n - i}x^i = x^nF(x^{-1})

易得F^T(x) = G^T(x) * H^T(x) + R^T(x)

所以F^T(x) \equiv G^T(x) * H^T(x) \mod x^{n-m+1}

所以F^T(x) * G^T(x)^{-1} \equiv H^T(x) \mod x^{n-m+1}

\begin{aligned} &\sum_{i = 0}^n(a_i+x-b_i)^2 \\ = &\sum_{i = 0}^n(a_i^2+b_i^2+x^2-2xb_i+2xa_i-2a_ib_i)\\ = &\sum_{i = 0}^n(a_i^2 + b_i^2) + x^2n + 2x\sum_{i = 0}^n(a_i-b_i)-\sum_{i = 0}^na_ib_i \end{aligned} (\sum_{i = 0}^nb_ix^i) (\sum_{i = 0}^na_ix^i) = (\sum_{i = 0}^{2n}x^i\sum_{j=0}^ia_jb_{i-j})\\ \end{aligned} \ln(F(x))=G(x) \Rightarrow \frac{F'(x)}{F(x)}=G'(x) \\e^{F(x)}=G(x) \Rightarrow F'(x)G(x) =G'(x) \\F(x)=\sum_{i=0}^na_ix^{i} \Rightarrow F'(x) =\sum_{i=1}^nia_ix^{i-1} \\F'(x)=\sum_{i=0}^na_ix \Rightarrow F(x)=C+\sum_{i=0}^n\frac{a_ix^{i+1}}{i} e^{F(x)} = G(x)\\ H(G_{\frac{n}{2}}(x))=ln(G_{\frac{n}{2}}(x)) - F(x)=0\mod x^{\frac{n}{2}}\\ H(G(x))=\sum_{i=0}^{inf}\frac{H^i(G_{\frac{n}{2}}(x))(G(x)-G_{\frac{n}{2}}(x))^i}{!i}\mod x^n\\ H(G(x))=H(G_{\frac{n}{2}}(x))+H'(G_{\frac{n}{2}}(x))(G(x)-G_{\frac{n}{2}}(x))=0

FWT

AND_FWT

c_i = \sum_{k \& j= i}b_ka_j\\ 设F_a(i) = \sum_{i\& j=i}a_j\\ F_a(i) * F_b(i) = \sum_{i\& j=i}a_j * \sum_{i\&k=i}b_k=\sum_{i\&(j\&k)=i}a_jb_k\\ F_c(i) = \sum_{i\&j=i}c_j=\sum_{i\&j\&k=i}a_jb_k\\

OR_FWT

c_i = \sum_{k | j= i}b_ka_j\\ 设F_a(i) = \sum_{i| j=i}a_j\\ F_a(i) * F_b(i) = \sum_{i|j=i}a_j * \sum_{i|k=i}b_k=\sum_{i|(j|k)=i}a_jb_k\\ F_c(i) = \sum_{i|j=i}c_j=\sum_{i|j|k=i}a_jb_k\\

XOR_FWT

c_i = \sum_{k \oplus j= i}b_ka_j\\ 设a\circ b = popcount(a\&b) \mod2\\ 所以(a\circ b) \oplus (a \circ c) = a\circ(b\oplus c)\\\ 设F_a(i) = \sum_{i\circ j=0}a_j-\sum_{i\circ j=1}a_j\\ \begin{aligned} F_a(i) * F_b(i) &= (\sum_{i\circ j=0}a_j-\sum_{i\circ j=1}a_j) * (\sum_{i\circ j=0}b_j-\sum_{i\circ j=1}b_j)\\ &=\sum_{(i\circ j) \oplus (i \circ k) = 0}a_jb_k-\sum_{(i\circ j) \oplus (i \circ k) = 1}a_jb_k\\ &=\sum_{i \circ (j \oplus k) = 0}a_jb_k-\sum_{i \circ (j \oplus k) = 1}a_jb_k\\ &=\sum_{i\circ j= 0}c_j-\sum_{i\circ j= 1}c_j \end{aligned} \\

111