位运算卷积指，给定两个长度为 $n$ 的数组 $a,b$，0-index，求数组 $c=a*b$ 满足 $c_k=\displaystyle\sum_{i\otimes j=k}a_i\times b_j$，其中 $\otimes$ 表示一种位运算。 分治乘法解决此类问题的思想是，对于任意一种位运算而言，不同的位之间互不影响，所以可以通过某种方式去…

题目是 AT_abc306_g [ABC306G] Return to 1 - 洛谷。 以下所有叙述均不考虑自环、重边。 上题本质上要求求出所有经过点 $1$ 的环环长的 gcd。 首先把包含点 $1$ 的强连通分量拿出来，显然只用考虑这个子图即可。 接下来考虑以 $1$ 为根建立任意一棵 dfs 搜索树，我们不加证明地给出一个断言：答案等于 $\…

散题 换根 DP： P3647 [APIO2014] 连珠线 - 洛谷 P2081 [NOI2012] 迷失游乐园 - 洛谷 树形 DP： AT_abc340_g [ABC340G] Leaf Color - 洛谷 P4253 [SCOI2015] 小凸玩密室 - 洛谷 P3687 [ZJOI2017] 仙人掌 - 洛谷 AT_agc034_e […

Krawtchouk 多项式定义为： $$ K_w(k,n)=\sum_{p=0}^{w}(-1)^p{k\choose p}{n-k\choose w-p}$$ 一个等价形式是 $$(1-x)^k(1+x)^{n-k}=\sum_{w=0}^{n}K_w(k,n)x^w$$ 线性递推公式指的是给定 $n,k$，可以在 $\Theta(n)$ 时间…

起因是发现自己脑子并不好使老忘。 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 …

这里用于记录我想记录的任何东西。