PE169
将 \(10^{25}\) 用二进制表示，从高位往低位 DP。
\(p_i = 1\) 时 \[ f_{i,1} = f_{i + 1,1} + f_{i+1,0}\\ f_{i,0} = f_{i+1,0} \] \(p_i=0\) 时 \[ f_{i,1} = f_{i+1,1}\\ f_{i,1} = f_{i+1,1} + f_{i+1,0} \]
PE643
有答案为 \[ \sum_{t=1}\sum_{i=1}^{\frac{n}{2^t}}\varphi(i) \] 直接用 Min-25 计算
PE605
不妨将胜负序列看成随机 01 序列，求第一次出现 01 的位置模 n 结果为每个数的概率是多少。
那么有下列 DP
\[ \begin{align*}\label{2 } & f_{i,01} = f_{i,00} = \frac{1}{2}(f_{i-1,10} + f_{i-1,00})\\ & f_{i,10} = f_{i,11} = \frac{1}{2}f_{i-1,11} \end{align*} \] 相当于两种值，不妨写出矩阵求和的形式，发现答案有递推式 \[ \begin{align*}\label{2} & g_{i,0}=\frac{1}{2}(g_{i-1,1} +g_{i-1,0})\\ & g_{i,1}=\frac{1}{2}g_{i-1,1} \end{align*} \] 并且有 \[ \begin{align*}\label{5} & g_{1,0}=\frac{1}{2}(g_{n,1} +g_{n,0})\\ & g_{1,1}=\frac{1}{2}(g_{n,1}+1) \end{align*} \] 手动解出答案为 \[ \begin{align*}\label{10} &g_{1,0}=\frac{n2^{n-1}}{(2^n-1)^2}\\ &g_{1,1}=\frac{2^{n-1}}{2^n-1}\\ &g_{k,0}=\frac{2^{n-k}(n+(k-1)(2^n-1))}{(2^n-1)^2} \end{align*} \] 分析下感觉不能约分，直接计算即可
####PE717
\[ \begin{align*} F(p)&=\lfloor\frac{2^{2^p}}{p}\rfloor\mod 2^p\\ &=\lfloor\frac{2^{2^p}}{p}\rfloor-\lfloor\frac{2^{2^p-p}}{p}\rfloor 2^p \end{align*} \]
令 \(a=2^{2^p}\mod p,b=2^{2^{p}-p}\mod p\) 有
\[ \begin{align*} F(p)&=\frac{2^{2^p}-a}{p}-2^p(\frac{2^{2^p-p}-b}{p})\\ &=\frac{2^{2^p}-a}{p}-\frac{2^{2^p}-b2^p}{p}\\ &=\frac{b2^p-a}{p}\\ \\ G(p) &= F(p)\mod p \\ &= \frac{b2^p-a}{p}\\ &= \frac{(b2^p-a)\mod p^2}{p} \end{align*} \]
所以对于确定 \(p\) 可以 \(O(\log n)\) 计算，一共 \(O(\frac{n}{\log n}\log n+ n)=O(n)\)