位运算卷积指，给定两个长度为 $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 搜索树，我们不加证明地给出一个断言：答案等于 $\…

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)$ 时间…