这里用于记录我想记录的任何东西。
位运算卷积指，给定两个长度为 $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 […
每日学习（常见 trick 之变换坐标轴）
典题是 AT_abc221_g [ABC221G] Jumping sequence – 洛谷。
另一个典题 AT_abc240_g [ABC240G] Teleporting Takahashi – 洛谷。
本题中，题面要求我们解决两个事情：决策 $D_i$ 分配给横坐标还是纵坐标，以及加还是减。
这个显然是不好做的，这就可以引出一种常见 trick。
考虑把 $(X,Y)\to(X+Y,X-Y)$，这显然是一个双射，我们可以发现原来的操作变成了：
- 向上：$(X,Y)\to(X+D,Y-D)$
- 向下：$(X,Y)\to(X-D,Y+D)$
- 向左：$(X,Y)\to(X-D,Y-D)$
- 向右：$(X,Y)\to(X+D,Y+D)$
容易发现这样我们不再需要决策 $D_i$ 分配给谁，同时横纵坐标对于每个 $D_i$ 而言的加减情况完全独立，只需要分开解决即可，显然可以使用 bitset 优化背包。
事实上，$(X,Y)\to(X+Y,X-Y)$ 是一种经典的 trick（在曼哈顿与切比雪夫的互相转化中亦有记载），他的本质是通过把横纵坐标结合起来减少限制，当发现题目中横纵坐标互相限制时，可以尝试使用此技巧。
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)$ 时间…