这里用于发布一些不成熟的想法和 P 话。 Hiiiiii...
每日学习
一棵无根树如果以某个点为根后，所有子树大小都小于 $\lfloor\frac{n}{2}\rfloor$，则这样的点至多只有一个，且必定是重心。
如果以某个点为根后，所有子树大小都小于等于 $\lfloor\frac{n}{2}\rfloor$，则这样的点至多只有两个，也必定是重心，且如果有两个，则这两个点一定直接有边相连。
重心的最大子树大小不会大于 $\lfloor\frac{n}{2}\rfloor$。
起因是发现自己脑子并不好使老忘。 DSU on tree 先树剖。 Func Modify = [] (int cur ,int op) -> void { if (op) max = std :: max (max ,tr.Query (a[cur]).first) ,tr.Insert (a[cur] ,0) ; else tr.Del …
我们设 $c_{i,j}$ 表示数组 $X_j$ 对变换数组 $FWT[X]_i$ 的贡献系数，有 $FWT[X]_i=\displaystyle\sum_{j=0}^{len-1}c_{i,j}X_j$。$c_{i,j}$ 使用人类语言表述就是所有下指标是 $j$ 的 $X$ 都对变换数下指标 $i$ 的位置有 $c_{i,j}$ 的贡献，值得注…
简单范德蒙德卷积式子
ABC 被我轻松开贺了，贺完学习一下。
范德蒙德卷积公式：$\displaystyle\sum_{i=0}^k {n \choose i}{m\choose k-i}={n+m\choose k}$，组合意义显然。
一个简单变式是 $\displaystyle\sum_{i=0}^m {n \choose i}{m\choose i}={n+m\choose m}$。
推论是 $\displaystyle\sum_{u\ge0} {x \choose u}{y\choose u+1}={x+y\choose y-1}$。
考虑直接 ${y\choose u+1}={y-1\choose u+1}+{y-1\choose u}$，于是变为 $\displaystyle\sum_{u\ge0} {x \choose u}{y-1\choose u+1}+\displaystyle\sum_{u\ge0} {x \choose u}{y-1\choose u}$。
对于前项，令 $v=u+1$，变为 $\displaystyle\sum_{v\ge1} {x \choose v-1}{y-1\choose v}$。
等价于 $\displaystyle\sum_{v\ge1} ({x+1\choose v}-{x\choose v}){y-1\choose v}$
所以原式等于 $(\displaystyle\sum_{v\ge0}{x+1\choose v}{y-1\choose v})-(\displaystyle\sum_{v\ge0}{x\choose v}{y-1\choose v})+(\displaystyle\sum_{u\ge0}{x\choose u}{y-1\choose u})=\displaystyle\sum_{v\ge0}{x+1\choose v}{y-1\choose v}$。
由变式得 $x+y\choose y-1$。
神奇取模/jy/jy/jy
做这个的时候看到的。牛逼结论：$(a\times c)\bmod(b\times c)=(a\bmod b)\times c$，两者任何情况下（包括非模意义下）完全相等。
考虑 $a=q\times b + r$，其中 $0\le r< b$，那么 $a\times c=q\times b\times c+r\times c$，则有 $\text{LHS}=\text{RHS}$。