三个旧理论的证明

· · 算法·理论

周期引理的代数证明

https://www.cnblogs.com/do-while-true/p/17604431.html

翻译自 https://zhuanlan.zhihu.com/p/85169630

字符串是 0-index．

周期引理：对于长为 n 的字符串 s，如果 p,q 均为 s 的周期，并且 p+q-\gcd(p,q)\leq n，那么 \gcd(p,q) 也是 s 的周期。

定义 s_p(i)=s_{i\bmod p},s_q(i)=s_{i\bmod p}，用生成函数来描述它，对于每个字符赋一个互不相等的权值作为系数，那么 s_p(x)=\frac{P(x)}{1-x^p},s_q(x)=\frac{Q(x)}{1-x^q}，其中 P(x) 是 p-1 次多项式，Q(x) 是 q-1 次多项式。

想要验证 s_p(x) 和 s_q(x) 完全相同，将两者作差得到 s_p(x)-s_q(x)=\frac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}\left(\frac{1-x^q}{1-x^{\gcd(p,q)}}P(x)+\frac{1-x^p}{1-x^{\gcd(p,q)}}Q(x)\right)，令 H(x)=\left(\frac{1-x^q}{1-x^{\gcd(p,q)}}P(x)+\frac{1-x^p}{1-x^{\gcd(p,q)}}Q(x)\right)．

假设 $H(x)\neq 0$，令它的最低位是 $h_tx^t$，则 $t\leq p+q-\gcd(p,q)-1\leq n-1$，那么 $[x^t]H(x)\frac{1-x^{\gcd(p,q)}}{(1-x^p)(1-x^q)}=h_t$，就得到 $\leq n-1$ 项的不为 $0$ 的系数，矛盾。所以 $H(x)=0$． 于是我们知道 $s_p(x)$ 与 $s_q(x)$ 完全相同，假设其为 $f(x)$，$p,q$ 同时为其周期。根据裴蜀定理，方程 $p\cdot u+q\cdot v=\gcd(u,v)$ 存在整数解，从而有 $s_i=f(i)=f(i+p\cdot u)=f(i+p\cdot u+q\cdot v)=f(i+\gcd(p,q))=s_{i+\gcd(p,q)}$，周期引理得证。 # 树上背包复杂度 https://www.cnblogs.com/do-while-true/p/16531718.html 多个子树可以三度化掉（当然这只是把树上背包合并的过程显式体现而已）在 dfs 序上考虑，合并子树看作合并这 dfs 序上相邻的两个区间，看作前面选择一个长度为 $x$ 的后缀，后面选择一个长度为 $y$ 的前缀，满足 $x+y\leq k$，它们拼成一个区间，方案数是多少。一个区间最多只会被拼出一次（也就是仅会在与它有交的子树都合并在一起的那一次被统计到），所以直接大力放缩成 dfs 序中所有长度 $\leq k$ 的区间，即得 $\mathcal{O}(nk)$ 的上界。 # Matrix Tree https://www.cnblogs.com/do-while-true/p/16526150.html 我们直接来证有向图内向树计数。考虑 $x$ 为根的内向树，对于除 $x$ 以外的每个点 $y$ 确定给一个 $fa_y$，那么就要求不能成环，考虑容斥，有一个环容斥系数就是 $-1$．考虑钦定若干个环，然后剩下的随便连。 我们尝试将其解释到 $x$ 的 $n-1$ 阶主子式上：如果排列中 $a_i=i$ 那么就说明 $i$ 是一个随便连 $fa$ 的点，方案数就是它的出度；一个大小为 $k$ 的环给逆序对奇偶性带来的贡献是 $(-1)^{k-1}$（每一次 swap 逆序对奇偶性改变）然后边的边权乘积是 $(-1)^k$，这样自然就凑出了容斥系数 $-1$．