小技巧

· · 个人记录

原文链接：小技巧

奇技淫巧

long double 快速乘

这么写据说不会出一点误差。

ll mul(ll x,ll y,ll mod) {
  ll c = (long double)x * y / mod + 0.5;
  c = x * y - c * mod;
  if (c < 0)    c += mod;
  if (c >= mod) c -= mod;
  return c;
}

贪心：

与一条条线段有关的贪心，若不会，则可以按端点排个序试试。

考虑贡献

拆贡献不仅可以在期望中用，还可以在计数中用。拆贡献通常能把复杂的问题简单化。

时光倒流

好多时候正着做不好做，倒着做会好很多。

补集转化/正难则反

有时候直接求解问题比较困难，考虑什么是不合法的，有时候会好很多。

最大值最小和最小值最大

最大值最小和最小值最大，除了考虑二分答案以外还要考虑贪心排序+微扰证明。

尤其是排序时有两个重量级相当的关键字，尝试计算其积或和或商或差或乘方来当作关键字排序，然后对拍证明之。

（如：国王游戏，危险游戏）

在图论中的最大值最小、最小值最大，可以考虑最小生成树或最大生成树来保证最优。 （如：the child and zoo,货车运输）

区间查询是否具有全部颜色

区间数颜色是个恶心的问题，通常需要离线莫队之类的算法。但是，如果只是问是否具有全部的颜色的话，就可以维护每个位置的pre。为了减少特判，通常在区间左、右边把所有颜色复制一遍。如果区间右边的所有的 pre 都不在区间的左边，就说明所有颜色都在区间中了。

详见：P4632 [APIO2018] New Home 新家

第k大

如果是序列上两两进行奇奇怪怪的操作，可以考虑P2048 [NOI2010]超级钢琴的做法，即P5283 [十二省联考2019]异或粽子的做法。

固定一个右端点，然后把它左边的最优答案扔到二叉堆里面。然后再找最大，删掉，转移区间分裂成两部分，然后再扔到二叉堆里面。

前驱后继的求法

这里的前驱后继定义为（不一定单调的）序列上前面第一个比 a_p 大的和后面第一个比 a_p 大的。

一种方法是从大到小排序后用 set 维护出现的点的位置，每次取 insert 的返回值。（insert 的返回值类型为 pair<iterator, bool>）

第二种方法是建出笛卡尔树，第 i 个点的子树为 l...r，那么前驱为 l-1，后继为 r+1。或者也可以用单调栈来实现。

离散化省去 lower bound 的一种做法

把编号记值上后排序，去重的时候顺便标记每个编号的排名。

这样就只有 sort 的 log 了。假设题目有特殊性质，比如能够一次归并来排序，就有可能优化到 O(n)。

小凯的疑惑

对于两个互质的正整数 a,b，不能通过 ax+by(x,y \ge 0) 表示出来的最大整数为 ab-a-b。证明考虑在模 b 意义下思考这个问题，那么 \{ak\},0 \le k < b 可以遍历 b 的剩余系。对于一个大于 a(b-1) 的数 n，考虑模 b 意义下为 t，那么可以找到一个 z 使得 az \equiv t，且 az \le n 加几个 b 即可，所以我们证明了 \ge a(b-1) 的数都能被表示出来。现在从 a(b-1)-1 开始往前数，一直到 a(b-1)-a+1 共遍历了 a-1 个 剩余系中其余的数，且这些数的 az 都比较小，再往前数一个数 a(b-1)-a 又回到 a(b-1) \mod b 了，但是这回就无法被表示出来了。

（所以还是直接当结论背过最好）

还有一种简洁明了的方法：将所有正整数表示成 ax+by 的形式，其中 x 取最小正整数解，发现 b 为负数的那些数表示不出来，其中最大的数为 a(b-1)-b = ab-a-b。

还有个类似的结论，是 SP11198 IPAD - Ipad Testing 里面的：a,b 互质的时候，不能被 ax+by 表示出来的数的个数为 \frac{(a-1)(b-1)}{2}，即从 1 到 (a-1)(b-1) 中恰有一半能被表示出来。这个目前找不到证明，背吧 陈神在上面简洁明了的那种方法的基础上搞出了一个类欧加皮克定理的方法，好神/se

枚举 (a * b) 的约数个数（约数和)

设 c_0(x) 表示 x 的约数个数， c_1(x) 表示 x 的约数和。

那么

c_0(a * b) = \sum_{i | a} \sum_{j|b} [gcd(i,j)=1]

这种枚举方式的实质是：将 a 和 b 质因数分解，如果 a = p^{c_1} * ..., b = p^{c_2} * ... ， i 带着某一个质因数幂 p^q，那么 j 必定不带，然后枚举的就是 p^{c_1 - q}；否则如果 j 带，就算枚举 p^{c_1 + q}，然后发现这样枚举因数是不重不漏的。此时的约数为 \frac{a}{i} * j

然后根据这个方法，可以枚举 c_1(a * b)：

c_1(a * b) = \sum_{i|a} \sum_{j|b} [gcd(i, j)=1] * (\frac{a}{i} * j)

然后可以依据这个来反演之类的。

φ(a*b)

因为 \varphi(x) = x\prod_{p|x}\frac1{p}，考虑用 \varphi(a) \cdot \varphi(b) 直接代替 \varphi(a \cdot b) 会多乘 \prod_{p|x,p|y}\frac1{p}，把它除掉即可。

\varphi(a \cdot b) = \frac{\varphi(a) \cdot \varphi(b) \cdot \gcd(a,b)}{\varphi(\gcd(a,b))}

疯狂除以 2 下取整

遇到某种约数只与\lfloor \frac{n}{2} \rfloor，\lfloor \frac{\frac{n}{2}}{2} \rfloor，... 有关的情况，可以转化为二叉堆上的链或子树问题。如：P4620 [SDOI2018]荣誉称号

数位和

在 B 进制下定义 d(x) = x,x < B，d(x) = d(digsum(x)), x \ge B。即 d(x) 表示 x 的数位和的数位和的...

这个时候发现每次都会把 B^k 转化为 1，即减去了 B^k - 1。而所有的 B^k-1 都会有 B-1 这个约数。

观察发现：d(x) = 0,x=0，d(x) = 1 + (x - 1 \mod B - 1)。（其实是不会证）

要求xxx被xxx整除，...?

有的时候，被xxx整除可以转化为 mod xxx 余数为0，这样或许更方便些。

带权中位数

即数轴上的点集中找到一个点 p，使得点集的所有点的 权值 × 到 p 的距离 的和最小。

我们可以使用微调的方法：

先假设 p 为最左面的点，算出来一个答案。然后再尝试将 p 移动到 p + 1，发现答案仅会变化 len * (lsum - rsum)。如果这个值为负，那么就移动并累加到答案，否则结束。依据此思想可以做：[P3286 [SCOI2014]方伯伯的商场之旅

](https://www.luogu.com.cn/problem/P3286)

实际上单纯求带权中位数，我们还可以直接拆点，转化为不带权的中位数。直接找 sum / 2 在哪里即可。

找到有根树中lca - ... - u的路径中lca下面的那个点

先树剖。然后从u一直向上跳，知道跳到lca那条重链上，并记录lst = top[u]。如果最终u与lca重合，那么答案为lst；否则为son[lca]。

Code: 
int Find(int x, int lca) {
    int lst = 0;
    while (top[x] != top[lca])  lst = top[x], x = fa[top[x]];
    return x == lca ? lst : son[lca];
}

二进制相关

二进制运算与进位加法结合

题目1 : 加的与 的和

加减乘除和位运算交叉的时候，一半考虑拆二进制位。第 i 位（从0开始) 为 1 可以转化为前 i 位在 1000...000 到 1111...111 之间，转化为范围问题，然后就可以支持部分加减法操作。

题目2 题目3：整体加1 与 异或和

如果要求支持不断加数删数，整体加一，以及求异或和的话，可以考虑维护一个反着的Trie，即从低位到高位的Trie。

因为整体加一实际上就是把每个数的尾巴上的那些1变成0，把那些1前面的那个0变成1.因此我们可以维护倒着的Trie来在尾巴上搞一些事情。（平时我们的Trie是从高位到低位是为了维护“子树内值连续”的性质，并且方便贪心，而这道题并不需要这种性质）

注意：01Trie也是可以合并的，就像同为二叉树的左偏树和线段树一样合并即可。

(甚至01Trie都可以当平衡树使，常数--，空间++（多个log），不过代码是真心短。）

重要代码：

inline void pushup(int cur) {
    siz[cur] = siz[son[cur][0]] + siz[son[cur][1]] + cnt[cur];
    xr[cur] = ((xr[son[cur][0]] ^ xr[son[cur][1]]) << 1) ^ (siz[son[cur][1]] & 1);
}
int merge(int rt1, int rt2) {
    if (!rt1 || !rt2)   return rt1 ^ rt2;
    son[rt1][0] = merge(son[rt1][0], son[rt2][0]);
    son[rt1][1] = merge(son[rt1][1], son[rt2][1]);
    cnt[rt1] += cnt[rt2];
    pushup(rt1);
    return rt1;
}
void modify(int cur) {
    if (!cur)   return ;
    swap(son[cur][0], son[cur][1]);
    if (cnt[cur])   {
        if (!son[cur][1])   son[cur][1] = ++ttot;
        cnt[son[cur][1]] += cnt[cur]; cnt[cur] = 0;
        pushup(son[cur][1]);
    }
    modify(son[cur][0]);
    pushup(cur);
}

BFS 的巧用

给一堆 S 和一堆 T，对每个 T 求出 S 中是否存在其子集。（值域 2^d）

如果先给 S 再给 T，就是个水题，直接记个桶，做个高维前缀和即可。复杂度 O(d2^d)

如果要求支持动态加 S 的话，可以来个 BFS,每次加 S 的时候暴力 BFS 其超集。因为每种状态只会被遍历一边，转移是 O(d) 的，所以均摊复杂度为 O(d2^d)

给一堆 S 和一堆 T，对每个 T 求出和 T 具有最多的公共 1 的 S。

如果先给 S 再给 T，就还是个水题。先对 S 做一遍高维后缀和，求出那些子集是合法子集。然后再以 siz 为权值做一遍高维前缀 max 即可。复杂度 O(d2^d)。

如果支持动态加 S 的话，可以每次 BFS 枚举之前没出现过的自己 P，再以 |P| 为权值枚举其超集 T ，用类似最短路一样的算法更新答案。复杂度是 O(d^22^d) 的，但是看起来还是比较快的， d=20 的数据 1s 内能跑出来。题

给一堆 S 和一堆 T，对每个 T 求出和 T 具有最多的公共位的 S。

如果先给 S 再给 T，可能还不是水题。目前我只会从上面那道 CF 题的做法中很牵强地拿出来。先对 S 按照 |S| （S 中 1 的个数）进行分类，对于 |S| = k_s 的类，设 |T| = k_t，S,T 公共 1 的位数为 k_1，那么不同的位数为 (k_s - k_1) + (k_t - k_1)，即我们需要最大化 k_1，转化为了上面那题。复杂度 O(n^2 2^n)。

如果支持动态加 S 的话，还是和上面那题一样跑类似最短路一样的算法。复杂度 O(n^32^n + qn)。目前还不会更优秀的做法 qwq

动态开点线段树不易下放标记？

如果动态开点不好下放标记，可以考虑标记永久化。但还是要求标记可加。具体操作是区间划分成的若干“小段”都打上标记，查询的时候把路过的标记都算上，如果是区间查询的话，还要记得加上最终“小段”的子树内的所有标记，因此还需每个点记个 val。即，我们要存俩数组：tag, val，其中 tag 表示“标记”，val 表示“当前子树中的所有标记的等效标记”。修改时所到之点都打 val，“小段”打 tag；查询时所到之点都考虑 tag，“小段”考虑 val。

具体代码见：P3332 [ZJOI2013]K大数查询

至于标记永久化，这道题应该是充分运用了此思想。

分治“被动”确定分界点不够平均？

UVA1608 不无聊的序列 Non-boring sequences 如果某一个题的分界点是题给的，需要我们自己找，那么如果这个分界点不够平均，就可能会因为查找分界点而卡到 O(n^2)。

一个解决方法是：我们同时从左右开始往中间找分界点，找到后立刻递归。这样，如果分界点在中间那正好，如果在两边，那么会早一点被找到，看起来会快一些。实际上，这么做的复杂度是 O(nlogn) 的。

区间逆序对？

逆序对不可直接加，但是可以拆，因此我们可以分块处理出块与块之间的逆序对数（如 f[i][j] 表示 i 块和 j 块的贡献）。同时顺便处理一下数的出现次数之类的东西。然后就可以 O(n\sqrt n logn) 做了。顺便说一下，这种做法是支持单点修改的。因此有：#3787. Gty的文艺妹子序列

求有向图的强连通子图数&生成DAG数

状压+容斥。

见bzoj 3812 [清华集训2014]主旋律。主要是要想到容斥，想到生成DAG数量，进而想到通过枚举出度为0的“强连通点”来容斥DP转移，还要想到把出度为0的“强连通点”中的所有点拿出来一起DP...总之还是很难的。

背包相关

DP用到状态不多

CF183D T-shirt

如果用到的状态不是很多，可以考虑记忆化搜索。如果懒得写记搜或嫌它慢，可以写动态开数组版的DP（通常用vector实现）

如果有用状态不一定连续，可以考虑把有用状态直接提取出来单独操作，实时去重。题 题

式子和区间划分，区间长度有关

即：AT2371 [AGC013E] Placing Squares

要求的式子是：

\sum_{所有划分} len^2

我们先考虑一个简单一点的问题：

\sum_{所有划分} len

假设我们想到了区间染色方案数问题，那么我们发现这实际上等价于任意划分区间，切要求每个区间有恰好一个点的方案数。我们规定点在数轴上 0~1 这个“块”中。

我们设 f[i][0/1] 表示考虑到1~n，最后区间有0/1个点的方案数，那么有：

f[i][0] <- f[i - 1][1]（新建一个区间） + f[i - 1][0]（这个位置不放点） f[i][1] <- f[i - 1][0]（放） + f[i - 1][1]（不放） + f[i - 1][1]（新建）

这样做的有点是可以矩阵加速：

f_{i,0} & f_{i,1}\end{bmatrix} * \begin{bmatrix} 1 & 1\\ 1 & 2 \end{bmatrix} = \begin{bmatrix} f_{i+1,0} & f_{i+1,1} \end{bmatrix}

（初始 f_{1, 0} = 1, f_{1} = 1)

这样的话，f_{n,1} 即为所求并且我们可以在 log 的时间内快速递推出来。

然后再考虑原来的那个问题：

\sum_{所有划分} len^2

类比可得，这等价于任意划分区间，切要求每个区间有恰好出现了一个1号点和一个2号点的方案数

我们设 f[i][0/1/2] 表示考虑到1~n，最后区间有0/1/2个点的方案数，那么有：

f[i][0] = f[i-1][0]（不放） + f[i-1][2](新建） f[i][1] = f[i-1][1]（不放) + f[i-1][0] * 2（放1/2号点) + f[i-1][2] * 2（新建并放1/2号点） f[i][2] = f[i-1][0]（放1,2号点) + f[i-1][1]（放剩下的那个点) + f[i-1][2]（不放) + f[i-1][2]（新建并放1,2号点）

然后就有：

f_{i,0} & f_{i,1} & f_{i,2} \end{bmatrix} * \begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 1\\ 1 &2 &2 \end{bmatrix} = \begin{bmatrix} f_{i+1,0} & f_{i+1,1} & f_{i+1,2} \end{bmatrix}

然后就可以快速递推了。

并且这玩意还能继续拓展，比如我们要求第 j “块” 和第 j + 1 “块”必须在同一个区间中，那么我们在递推 j -> j + 1 的时候可以对矩阵略加修改，删去“新建”操作带来的方案数：

f_{i,0} & f_{i,1} & f_{i,2} \end{bmatrix} * \begin{bmatrix} 1 & 2 & 1\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} f_{i+1,0} & f_{i+1,1} & f_{i+1,2} \end{bmatrix}

这样就可以做 AT2371 这道题了。不过现在洛谷交不了，AT登不上，VJ未收录，可能要等一段时间

2021.3.11 Update：半年后鸽子终于写了这道题！

树上每个点能到达的最近点

题目：世界树, Cow at Large P

题解：P3233 [HNOI2014]世界树

可以正着DFS一遍，记录最近点在子树中的情况；然后再DFS一遍，用父亲去更新儿子（因为此时父亲的答案已经正确了）

树形差分

题目：Cow at Large P

要求一棵子树的每个节点都要贡献，但是总共的贡献和为 1。

一棵子树（整棵树除外）的点的度数的和为 2siz - 1，即：

\sum_{i}d_i = 2siz - 1

移项：

\sum_{i}2 - d_i = 1

这样，如果每个点的贡献是 2 - d_i 的话，整棵子树的贡献就是 1.（神奇）

点减边容斥

题目：希望（咕咕中）

有若干合法连通块，要求每个连通块只被计算一次，问合法连通块数。

存在 快速计算包含一个点（或一条边）的合法连通块的答案 的方法。

一个连通块的点数和边数的关系是 m=n-1，所以 n-m=1。于是用点算一遍，再用边算一遍，减一下即可。

区间查询问题的一种方法

区间查询问题通常可以用线段树或莫队解决，但是有些时候它们都无法解决，这时候有一种方法:把所有询问挂到右端点上，然后扫描原序列，并维护从右往左的答案，有时候这样或许会好做一些。

例题：51nod 1577 异或凑数； Comet OJ - Contest #14D 转转的数据结构题

bool 类型的DP数组

遇到 bool 类型的DP数组一定要想 bitset 优化啊！！这是个套路！这题 这题

好吧，更有效的方法是将可行性问题转化为最优性问题（如果可以的话)，比如这题和这题，把越大（小)越好的东西记录在值里面，通常能砍掉一维。

数论推式子可能用到的

欧拉函数对称性

\sum_{i=1}^n i[(i,n)=1]=\frac{n \varphi(n)}{2}

因为对于任意一个与 n 互质的数 i，n-i 一定也与 n 互质，于是我们可以将 i 两两配对，每一对的值都是 n（就算有 n-i=i，我们也可以认为这是半对）

唯一的特例是 n=1，此时与 1 互质的数有 1,0，但我们在算 \varphi(1) 的时候并没有算进去 0，于是特判一下就好。

贡献差分前缀和代替整除分块

考虑式子：

f(n) = \sum_{i=1}^n h(i)g(\left \lfloor \frac{n}{i} \right \rfloor )

显然可以通过对 h 前缀和 + 整除分块做到 O(n+T\sqrt n) 的复杂度。但是当 T \ge 10^6 的时候可能就不行了。

我们可以考虑每一个 h(i),g(\left \lfloor \dfrac{n}{i} \right \rfloor ) 的贡献，即枚举 i,\left \lfloor \dfrac{n}{i} \right \rfloor 。对于一个 i 来说， \left \lfloor \frac{n}{i} \right \rfloor = t 的 n 的位置为 it... it + i - 1，于是我们可以直接打差分标记，最后前缀和一遍即可。注意到对于一个 i，有用的 t 只有 n / i 个（n 为最大的 n），因此复杂度为：O(n \ln n + T)

0~3自然数幂和

$m=2$: $$ \sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} $$ $m=3$ 的自然数幂和。 $$ \sum_{i=1}^ni^3=(\sum_{i=1}^ni)^2=\frac{n^2(n+1)^2}{4} $$ 最好直接记住，就不用现推伯努利数了。 ### μ^2 $$\mu^2(x)=\sum_{d^2|x}\mu(d)$$ 考虑 $d^2|x$ 这个限制，如果 $x$ 的质因数分解中为 $p_i^{c_i}$，那么 $d$ 最多为 $p_i^{c_i/2}$。于是可以知道 $d^2|x$ 实际上相当于 $d|x'$，当 $x$ 存在平方因子的时候 $x' > 1$。而右面的式子相当于 $\mu * 1 = \epsilon$。 应用： 求: $$\sum_{i=1}^n \mu^2(i)$$ 其中 $n \le 10^{18}$。 考虑用上面的那个式子来代替 $\mu(i)$： $$\begin{aligned} \sum_{i=1}^n\mu^2(i) &= \sum_{i=1}^n\sum_{d^2|i}\mu(d)\\ &= \sum_{d = 1}^{\sqrt n}\mu(d)\left \lfloor \frac{n}{d^2} \right \rfloor \end{aligned}$$ 可以暴力做到 $O(n^{0.5})$。用类似整除分块的方法套上杜教筛能做到大约 $O(n^{0.4})$。 ### id = φ * 1 当遇到 $[(i,j)=1]$ 的时候考虑转 $\mu$，但是遇到 $(i,j)$ 的时候最好还是用 $\phi$。 ### 欧拉函数的一些应用 $$ \sum_{i=1}^n [(i,k)=1] $$ 当 $k$ 比较小的时候，这个式子可以优化到 $O(k)-O(1)$。因为当 $i > k$ 时会出现循环，我们只需要求一下有多少个循环，再预处理一下零散块的前缀和即可。 ### 斐波那契的一些性质 详见 [oi-wiki](https://oi-wiki.org/math/fibonacci/) 通常情况下，我们认为 $F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2...

那么有：

F_{n+k}=F_nF_{k-1}+F_{n+1}F_k

建议感性理解或感性记忆一下。

然后就可以推出一堆好玩的性质:

F_{2n}=F_n(F_{n+1}+F_{n-1})\\ F_k | F_{nk}\\ \forall F_{a}|F_{b},a|b\\ \gcd (F_a,F_b) = F_{\gcd(a,b)}

比较常见的形式：f_af_b+f_{a+1}f_{b+1}=f_{a+b+1}

据此可以得出递归求斐波那契的式子：

f_{2n}=f_nf_{n-1}+f_{n+1}f_n = f_n(f_{n-1} + f_{n+1}) = f_n (2f_{n+1}-f_n)\\ f_{2n+1}=f_n^2+f_{n+1}^2 
PII get_f(int n) {//f[n], f[n + 1]
    if (n == 0) return MP(0, 1);
    PII pr = get_f(n >> 1);
    int a = pr.first * (2 * pr.second - pr.first);
    int b = pr.first * pr.first + pr.second * pr.second;
    return n & 1 ? MP(b, a + b) : MP(a, b);
}

会比矩阵加速要快一些。

在模 p 意义下，斐波那契数列存在循环节，且循环节长度不超过 6p。具体求循环节的方法见我的博客

还有一个显然但不可忽略的性质：\gcd(F_n,F_{n-1}) = 1

下取整和约数个数

有一个比较好用的式子：\lfloor \frac{n}{i} \rfloor = \sum_{i|d}1，即 n 以内的 i 的倍数个数。

形式一

\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor = \sum_{i=1}^n \sigma_0(i)

证明：

\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor = \sum_{i=1}^n \sum_{i|d}1 = \sum_{d=1}^n\sigma_0(d)

形式二

\sum_{i=1}^n \lfloor \frac{n}i \rfloor * i ^k = \sum_{i=1}^n\sigma_k(i)

证明：

\sum_{i=1}^n \lfloor \frac{n}i \rfloor i^k= \sum_{i=1}^n \sum_{i|d}i^k = \sum_{d=1}^n\sigma_k(d)

线性筛约数个数和

depri[1] = true; g[1] = 1;
for (int i = 2; i <= up; ++i) {
    if (!depri[i])  pri[++pcnt] = i, g[i] = i + 1;
    for (int j = 1; j <= pcnt && i * pri[j] <= up; ++j) {
        depri[i * pri[j]] = true;
        g[i * pri[j]] = g[i] * g[pri[j]];
        if (i % pri[j] == 0) {
            g[i * pri[j]] -= pri[j] * g[i / pri[j]];
            break;
        }
    }
}

Dirichlet 卷积和高维前缀和

$B(n) = \sum_{n | d} A(d)$ ： 高维后缀和 $B(n) = \sum_{d | n} A(d) \mu(n / d)$（卷 $\mu$）：高维差分。 通过枚举每一维做可以做到 $O(\sum_{p \in Prime} n/p) = O(n \log \log n)$。 ## 二项式系数与递推 不得不说，因为加法公式 ${n \choose m} = {n-1 \choose m} + {n-1 \choose m - 1}$，所以二项式很适合拆开递推。 例如，在[这道题](https://www.luogu.com.cn/problem/P6031)中，$S(t)=\sum_{i=0}^{k-t}(-p)^i {n-t \choose i}$ 可以这样递推： $$ \begin{aligned} S(t) &= \sum_{i=0}^{k-t} (-p)^i {n - t \choose i} \\ &= \sum_{i=0}^{k-t} (-p)^i ({n-t-1 \choose i} + {n-t-1 \choose i-1})\\ &= \sum_{i=0}^{k-t} (-p)^i {n-t-1 \choose i} + \sum_{i=0}^{k-t} (-p)^i {n-t-1 \choose i-1}\\ &= (1-p)S(t+1) + (-p)^i {n-t-1 \choose k-t} \end{aligned} $$ ## 多项式组合计数可能用到的 ### 减法卷积 卷积类似 $f_n = \sum_{i \ge n} g(i) h(i-n)$ 的时候，可以翻转 $g(i)$，即设 $g'(i) = g(m-i)$，那么 $f_n = \sum_{i \ge n} g'(m-i)h(i-n)$，这样 $\sum_{i \ge n}g'(m-i)h(i-n)$ 卷积后会到 $m-n$ 的位置，于是将卷积答案翻转一下即可。 ### 二项式反演的优化 形如 $$ f(i) = \sum_{j \ge i} g(j) {j \choose i} (-1)^{j-i} $$ 拆开组合数后发现是个减法卷积。 ### 套娃 对于某种组合对象 $A$，其生成函数为 $A(x)$；由这种组合对象组成的**集合**的生成函数为 $\sum_{i} \frac{A^i(x)}{i!} = exp(A(x))$;由这种组合对象组成的**序列**的生成函数为 $\sum_i A^i(x) = \frac{1}{1-A(x)}$。 ### 求生成函数 n 次方的 k 阶导 即求 $$ (F(x)^n)^{(k)} $$ 有个组合意义：$n$ 个 $F(x)$ 排成一排，做 $k$ 次，每次对一个 $F(x)$ 求导（可以对同一个 $F(x)$ 多次求导），然后乘一块，最后的答案为所有可能的方案的乘积的和。（可以试着对着 $n=2$ 和 $n=3$ 的情况手玩一下） 如果知道 $F(x)^{(k)}=g_k$，那么可以表示成生成函数的形式： $$ (F(x)^n)^{(k)} = k![x^k](\sum_i \frac{g_i }{i!} x^i)^n $$ ### 点值和系数的乘积与 k 阶导数 求： $$ \sum_i F(i) \cdot [x^i] G(x) $$ 其中 $F(i)$ 表示点值。 套路是把 $F(i)$ 转化为下降幂多项式 $\sum_i f_i x^{\underline{i}}$： $$ \sum_i \sum_k f_k i^{\underline{k}} \cdot [x^i] G(x)\\ = \sum_kf_k \sum_i i^{\underline{k}} \cdot [x^i] G(x)\\ = \sum_k f_k G^{(k)}(1) $$ （因为右边部分恰好是 $k$ 阶导后的系数和） ## 高阶前缀和 ~~众所周知~~，对一个序列求前缀和就是卷上 $\frac{1}{1-x}$，于是 $k$ 阶前缀和就是 $\frac1{(1-x)^k}$。二项式定理展开并上指标反转： $$ \frac{1}{(1-x)^k} = \sum_i {-k \choose i} (-x)^i = \sum_i {i-k-1 \choose i} x^i $$ 其实还可以考虑组合意义： $$ [x^n]\frac{1}{(1-x)^3} = \sum_{i=0}^n \sum_{j=0}^i 1 = {n + 1 - (3-1) - 1 \choose 3-1} = {n-3+1 \choose n} $$ 即：$n$ 个小球中选 $k$ 个小球（可重）方案数为 ${n + k - 1 \choose k}$，可以将第 $i$ 个小球的位置 $+i-1$，就成不可重了。 ## 判断某数是否在模意义下在某个区间内 例题：[Maximum Sine](https://www.luogu.com.cn/problem/CF1182F) $$ [x \in [l,r](\bmod p)] = \lfloor \frac{x-l}{p} \rfloor - \lfloor \frac{x-(r+1)}{p} \rfloor $$ ## 快速求三角形外接圆半径 已知三角形三点坐标，求三个点的外接圆半径。 我们当然可以用解析几何大法搞出俩中垂线，然后联立求圆心，然后求距离即为半径，但是那样太麻烦了，我们只要半径就好。 一种方法是：算出三边长度和三角形面积（叉积），然后 $$R=\frac{abc}{2S}$$ 这是因为： $$\frac{abc}{2S}=\frac{abc}{2absinC}=R$$ （正弦定理） ## 多重背包是可以优化的啊！！ 比较弱的优化有二进制拆分，比较强的优化有单调队列或者前缀和优化。不要光想着用暴力啊！！！ ## 最少乘法划分 > 将 $n$ 个数划分为若干集合，每个集合的代价为集合内的数的乘积。要求集合代价不超过 $m$。求最少能划分为几个集合。 有可能会想从小到大一直尝试，不行就再来个新集合。但这是错的，因为到了较大的数的时候可能两个数乘起来就超过 $m$ 了，只能一个一个地装。但是可能还可以容得下一些小数。因此最优方案应该是一个大数配上几个小数。可以用双指针实现。 ## 差分优化建图 例题：[Tax](https://www.luogu.com.cn/problem/P6822)；[通信](https://www.luogu.com.cn/problem/P5331) 最大值，绝对值等可以使用差分优化建图 ## 最大团 = 补图最大独立集 例题：[朋友圈](https://www.luogu.com.cn/problem/P2423) 众所周知，最大团是个NPC问题，但是最大独立集有时候（如二分图上）是有快速解法的。 ## DP的两种递推方式 众所周知，DP大致有两种转移方式：考虑由谁转移而来；考虑要贡献到哪里去。 有的时候第一种转移要更好做（更好前缀和优化之类的），有的时候第二种转移更好想（[题](https://codeforces.com/contest/822/problem/E)） ## 数列递推求通项（特征根法） $a_n = pa_{n-1} + qa_{n - 2}$，则把它看作 $x^2 = px + q$，解方程。 如果无实根，那么序列 $a_i$ 一定是周期的，即存在 $t$，使得 $a_i = a_{i+t}$。 如果有两相等实根 $x$，那么 $a_n = (Cn+D)x^{n}$。 如果有两个不等实根 $x_1,x_2$，那么 $a_n = Cx_1^n + Dx_2^n

然后随便代入俩值求解出 C,D 即可。

生成函数求通项

关键在于化为 \frac{1}{1-cx} 的形式。因为 \frac1{1-cx} = \sum_i c^ix^i，是我们可以快速求通项的形式。

例如，尝试快速求 \frac{1}{ax^2+bx+c}(b^2-4ac \ge 0) 的通项。首先可以尝试将 ax^2+bx+c 因式分解：求出两根 x_1,x_2，那么这个式子可以化为 a(x-x_1)(x-x_2)。然后就是要解决 \frac{1}{(x-x_1)(x-x_2)}，可以拆开：k(\frac{1}{x-x_1} - \frac{1}{x-x_2})，然后将常数项化为 1：k'(\frac{1/x_1}{1-k_1'x} - \frac{1/x_2}{1-k_x'x})，然后套用 \frac1{1-cx} = \sum_i c^ix^i 即可。题

当然，有些式子并不好化为 \frac{1}{1-cx} 的形式，此时可以尝试其它方法。例如：

F(x) = (1+qx)^{c-1}(1+x)^{n-c}

的通项求法可以通过求导的方法来得出：

F'(x) = q(c-1)\frac{F(x)}{1+qx} + (n-c)\frac{F(x)}{1+x}

而这个除 (1+qx) 和 (1+x) 不太好处理，如果是乘法就会好处理很多。于是可以两边同时乘 (1+qx)(1+x)：

(1+x)(1+qx) F'(x) = q(c-1)(1+x)F(x) + (n-c)(1+qx)F(x)\\ ...f_{n-1} + ...f_n + ...f_{n+1} = ...f_{n-1} + ...f_n\\ f_{n+1} = ...f_{n} + ...f_{n-1}

题

k次斐波那契求和

定义 f_0=0,f_1=1,f_n=f_{n-1}+f_{n-2}，求：

\sum_{i=1}^n f_i^k \pmod {10^9+9} 1 \le n \le 10^{18},1 \le k \le 10^5

由于是 k 次的斐波那契，矩阵快速幂不好使了。又显然不能一个一个地递推，我们只好换一种方法。

众所周知：

f_n = \frac{(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n}{\sqrt 5}

化成普通幂的形式要好算得多。

\begin{aligned} ans &= \sum_{i=1}^n f_i^k\\ &= \sum_{i=1}^n (\frac{(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n}{\sqrt 5})^k\\ \end{aligned}

还是不好搞，于是二项式暴力展开：

ans = \sum_{i=1}^n \sum_{d=0}^k {k \choose d} (\frac{\varphi^i}{\sqrt 5})^d (\frac{-\hat{\varphi}^i}{\sqrt5})^{k-d}

交换求和号化简得：

ans = \sum_{d=0}^k {k \choose d}\frac1{\sqrt 5^k(-1)^{k-d}} \sum_{i=1}^n (\varphi^d \hat{\varphi}^{k-d})^i

等比数列求和即可。

如果忘了怎么求二次剩余，或者没有 5 的二次剩余的话，可以写一个类似复数的东西，(a,b) 表示 a+b\sqrt5，逆元可以手动解方程。

复杂度：O(k \log n)

一个概率期望的结论

对于 n 个在 [0,1] 间均匀随机取值的随机变量，其第 k 小的值的期望为 O(\frac{k}{n+1})，即：

E(kth) = \frac{k}{n+1}

其拓展为取值范围为 [0,RandMax] 的情况：

E(kth) = \frac{k}{n+1} \cdot RandMax

这个结论可以做一些随机化算法的题，同时也是某些概率期望题的前置知识

多边形重心

对于一个多边形 P，区域 D=\{(x,y)|(x,y) \in P\}。重心定义为：

(\int \int_D x dx dy,\int\int_D ydxdy)

（即区域内横坐标加权平均和纵坐标加权平均）

对于三角形 ABC，其重心为：

(\overline{x},\overline y)

对于任意多边形，其重心为三角剖分后各重心的对面积的加权平均。注意这里的面积是有向面积。

注意，(\overline x,\overline y) 这个公式对于三角形以外的多边形来说是错误的。实测（随便造了个凸六边形）和上述做法的结果完全不一样。

计算几何中的直线

如果不嫌麻烦的话，可以用解析几何的那套方法，y=kx+b 来记录直线。

如果用到的直线都是过给定的点的话，可以用两点记录直线，用叉积判断点是否在直线上。这样就没有精度误差了（如果给定的点坐标均为整数）

基于值域预处理的快速 GCD

有一种O(值域)预处理O(1)查询的gcd算法。

首先对于 \gcd(a,b)，有一个数是素数或者小于 \sqrt v （v 为值域）的情况是好处理的（模一下就都小了）

尝试将 v 以内的数都分解成 O(1) 个质数或小于 \sqrt v 的数后 O(1) 就可以 O(1) 求 gcd 了。

可以证明所有数都可以被分解为不超过 3 个素数或小于 \sqrt v 的数，方法是线性筛，对于最小质因子为 p 的 n，在 n 的那三个数中挑一个最小的，把 p 乘上去。

模板

两端插入删除区间查询

普通前缀和数组可以支持后端插入删除区间查询，而如果在前端插入的话，除了打区间加标记以外，还可以在前面减数来调整到正确。原理是我们只需要保证差分正确即可。可以手玩一下。代码：

int que[NN], sum[NN], front, rear;
inline void push_front(int x) { que[front--] = x; sum[front] = sum[front + 1] - x; }
inline void push_back(int x) { que[rear] = x; sum[rear] = sum[rear - 1] + x; }
inline void pop_front() { sum[front] = 0; ++front; que[front] = 0; }
inline void pop_back() { sum[rear] = 0; que[rear] = 0; --rear; }
inline int query(int l, int r) { return sum[front + r] - sum[front + l - 1]; }

牛顿迭代求逆元

对于模数为 2^{32} 的题来说非常好使。原理和多项式求逆一样，可以把数看作二进制高精。

只用五次简单运算即可得到答案，复杂度是 O(\log \log P) 的，几乎可以看作 O(1)。

    const ull mod = (1ull << 32);
    inline ull get_inv(ull A) {
        ull B = 1;
        B = B * (2ull - A * B);
        B = B * (2ull - A * B);
        B = B * (2ull - A * B);
        B = B * (2ull - A * B);
        B = B * (2ull - A * B);
        return B;
    }

库默尔定理

证明： $n!$ 中质因子 $p$ 的指数为 $\sum_k \frac{n!}{p^k}$。对于 $n \choose m$ 中的第 $k$ 次来说，对答案的贡献为 $$ \lfloor \frac{n!}{p^k} \rfloor - \lfloor \frac{m!}{p^k} \rfloor - \lfloor \frac{(n-m)!}{p^k} \rfloor $$ 而这个东西大部分时候都是 $0$，除了 $m + (n - m)$ 在第 $k$ 位进位的时候为 $1$。 ## 有时间顺序的网络流 可以考虑按照时间分层建图。 参考：[星际转移问题]([P2754 [CTSC1999\]家园 / 星际转移问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P2754))，[收藏家]([收藏家 - 题目 - 信息学在线评测系统 (sjzezoj.com)](https://sjzezoj.com/problem/340))，[古代游戏记录]([古代游戏记录(record) - 题目 - 信息学在线评测系统 (sjzezoj.com)](https://sjzezoj.com/problem/366)) ## 快速求所有前缀积的 gcd 求所有的 $i$ 的 $S_i = \gcd(a, \prod_{j=1}^i b_j)$。 先求出所有的前缀积（模 $a$），记为 $mul_i$，算出最右边的答案 $S_r$，那么 $S_i = \gcd(S_{i+ 1}, mul_i)$。复杂度 $O(n + \log)$。 ## 一种哈密顿路径题目的常见做法 实时维护一条（或多条）哈密顿链 ## 树同构 一种常见的方法是树哈希判断同构，如果是无根树的话要么枚举根后对 Hash 值集合进行哈希，要么把重心作为根。 还有一种比较暴力但常常用来 DP 的方法，是枚举各**对应点**到底是啥。比如可以枚举根后设 $f(i,j)$ 表示 $i,j$ 子树是否同构，转移类似匹配，可以状压或暴力网络流跑匹配。 当然，不排除 [树](https://www.luogu.com.cn/problem/P4500) 之类的毒瘤群论去重法。 ## 数树经典结论 - 有 $m$ 棵小树，第 $i$ 棵小树的大小为 $v_i$，$n = \sum_i v_i$，再在它们之间加一些边连成大树的方案数为 $n^{m-2} \times \prod_i v_i

有 prufer 证明和 matrix tree 证明。这里给出 prufer 证明。

首先直接 m^{m-2} 是不对的，这是因为第 i 棵树的度数为 d 的时候要贡献 v_i^d。重新考虑 prufer 序列，枚举每棵树的出现次数：

\begin{aligned} & \sum_{\sum d_i = m - 2} (\frac{m!}{\prod_{i} d_i!}) \times (\prod_i v_i^{d_i + 1}) \\ &= (\prod_i v_i) \times \sum_{\sum d_i = m - 2} (\frac{m!}{\prod_i d_i!}) (\prod_i v_i^{d_i}) \end{aligned}

考虑后面的组合意义，为先给每棵小树分配位置，第 i 棵小树的一个位置的贡献为 v_i。我们不妨直接给位置确定小树，乘上它的贡献，显然位置之间相互独立，于是每个位置的贡献为 \sum v_i = n，所以右边那块就等于 n^{m-2}。于是答案为 n^{m-2} \times \prod_i v_i。

这个结论使用范围很广，只要 n 个点的完全图的边 (u,v) 的权值为 a_u \times a_v，那么这张完全图的生成树的权值和为 (\sum_{i} a_i)^{n-2} \prod_i a_i（生成树权值为边权值之积）

两两最短路之和

树上的话通常考虑贡献。

特殊图（如网格图）上经常要考虑分治。

生成树

有的时候一般图不好做，可以考虑是不是能够转化为dfs树或者最小生成树上的问题。通常转化后会好做一些。

通配符

对于一些和“两字符串的不同位置”有关系的题可以考虑使用通配符来加速查找。题

“奇偶性”计数

Beautiful fountains rows：若干球，第 i 种球会出现在 l_i...r_i 的所有位置上。问所有有球的位置区间中每种球都出现了奇数次的区间的长度之和。 n \le 2 \cdot 10^5, 1 \le l_i \le r_i \le 2 \cdot 10^5

有个套路：给每种球随机一个权值，问题转化为区间所有球的异或等于区间出现过的球的异或。

这个题中，区间异或很好处理，区间出现过的球的异或可以转化为所有球的异或除掉没有出现过的球（完全在左边 + 完全在右边）的异或。这样就好搞了，那个哈希表随便搞搞即可 O(n)。

当然也有很多类似的题

树计数

有标号无根树计数可以考虑 prufer 序列，matrix tree，或者枚举根节点后跑完美匹配或状压。

强制父亲标号小于儿子的话可以考虑加子树，方便乘组合数，但是也不排除有按编号排序选爸爸的题。题

无标号难点在于去重，可能需要枚举根节点，想办法去重（如把儿子按编号排序），还要注意有两个根的情况。题

有时候考虑拆儿子也可能有妙用。题 题

模意义下 O(1) 快速乘除法

维护个结构体。把逆元也维护上就可以 O(1) 除了（但是可能需要预处理带 log）

struct Num {
    int c;
    ll x, y;//num, inv(num)
    Num(){c = 0, x = 1, y = 1; }
    Num(int jzp, ll zzz, ll lsr) { c = jzp, x = zzz, y = lsr; }
    inline Num operator +(const Num &a) const {
        return Num(c + a.c, x * a.x % P, y * a.y % P);
    }
    inline Num operator -(const Num &a) const {
        return Num(c - a.c, x * a.y % P, y * a.x % P);
    }
};

排列逆序对奇偶性的简单求法

将排列看作若干循环，则排列的逆序对奇偶性为偶环的个数的奇偶性。

证明：交换一条环上的边会导致逆序对奇偶性变化一下（排列上交换两个数），环大小会减少一.于是答案为 环边 - 环数 的奇偶性，即偶环个数的奇偶性。

一种计算特殊矩阵的行列式/积和式

（积和式就是行列式去掉 (-1)^{\sigma(p)} 的部分）

对于矩阵 C = A + B，其中 a_{i,j} = x，B 矩阵为稀疏矩阵，那么 c_{i,j} = a_{i,j} + b_{i,j}，计算时可以拆成一些位置选 B，剩下的位置选 A。行列式选 A 几乎都是 0，积和式选 A 是阶乘，都是比较好算的形式。

树形删边博弈

有根树，先后手轮流删边，删掉一条边后那棵子树消失，无法操作者输。

结论：一棵树的 SG 值是其所有子树的 SG 值加一的异或。即 SG(T_r) = \bigoplus_{r \to u} (SG(T_u) + 1)。

证明需要归纳，详见 2009 年 jzh 的集训队论文。

基尔霍夫矩阵树定理的妙用

缩一二度点

如果题目保证图连通且 m-n 非常小，可以通过缩一二度点来减小数据规模。

可以证明，如果每个点的度数都至少是 3，点数是 O(m-n) 级别的。

对这张度数至少为 3 的图搞一个生成树，考虑最少加多少非树边才能满足度数要求。对于假设叶子节点有 a 个，还有 b 个（仅考虑树上的度数）二度点和 c 个更多度的点。那么有 c \le a，一个叶子需要 2 个非树边度数，还可能要给一个“更多度数的点”均一均，就是 1 个非树边度数。一个二度点需要 1 个非树边度数，所以总共最多造出来 \frac{n}2 条非树边。于是如果 M-N = n，那么点数应该是 2n 左右。

平面图对偶图生成树

将平面图对偶图的生成树上的边对应的平面图上的边删掉后平面图也会只剩下一个生成树（一一对应）