标签：begin end 题解 sum sqrt choose 东西 一些 aligned

A

TBA

B

设 \(f_{i,0/1}\) 表示 \(i\) 子树 DFS 序奇 / 偶位置和的最大值，

首先如果 \(i\) 所有孩子的子树大小都是偶数，那访问这些孩子的顺序就无所谓了，

否则考虑以 \(i\) 的至少一个大小为奇数的孩子为分界，

对所有大小为偶数的孩子 \(v\)，把 \(f_{v,0}\) 更大的 \(v\)、\(f_{v,1}\) 更大的 \(v\) 分别放在其两侧，

这样就可以对所有 \(v\) 取到 \(\max(f_{v,0},f_{v,1})\) 的贡献。

然后考虑剩下 \(c\) 个大小为奇数的孩子 \(v\)，可以发现一半 \(v\) 取到 \(f_{v,0}\)，一半 \(v\) 取到 \(f_{v,1}\)，贪心即可。

C

对每个 \(1\) 的位置 \(i\)，考虑 \(\text{LCP}(x,n)=i-1\) 的 \(x\) 的贡献，

即考虑 \([1,i-1]\) 位与 \(n\) 相同，\(i\) 位填 \(0\)，后面 \(n-i\) 位任意填的数的贡献。

设 \(k=n-i\)，前 \(i-1\) 位中有 \(c\) 个 \(1\)，则这些数的贡献为：

\[\sum_{i=0}^k{n\choose i}f_{i+c} \]

Sol 1

设 \(x_1=\dfrac{1+\sqrt 5}2\)，\(x_2=\dfrac{1-\sqrt 5}2\)，则：

\[\begin{aligned} &\sum_{i=0}^k{n\choose i}f_{i+c}\\ =&\dfrac 1{\sqrt 5}\left(x_1^c\sum_{i=0}^k{n\choose i}x_1^i-x_2^c\sum_{i=0}^k{n\choose i}x_2^i\right)\\ =&\dfrac 1{\sqrt 5}\left(x_1^c(x_1+1)^k-x_2^c(x_2+1)^k\right) \end{aligned} \]

预处理需要预处理的东西即可。

\(5\) 好像不是二次剩余，直接扩域。

Sol 2

设 \(F=\begin{bmatrix}0&1\end{bmatrix}\)，\(B=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)，\(I\) 为单位矩阵，则

\[\begin{aligned} &\sum_{i=0}^k{n\choose i}f_{i+c}\\ =&F\times B^c\sum\limits_{i=0}^k{n\choose i}B^iI^{n-i} \end{aligned} \]

显然 \(B\) 和 \(I\) 有交换律，那么

\[\begin{aligned} &F\times B^c\sum\limits_{i=0}^k{n\choose i}B^iI^{n-i}\\ =&F\times B^c(B+I)^k \end{aligned} \]

预处理需要预处理的东西即可。

标签：begin,end,题解,sum,sqrt,choose,东西,一些,aligned
From： https://www.cnblogs.com/5k-sync-closer/p/18263480