FFT类

1. 求Bit数

容斥或者反演和ntt，一道组合数学的题目，字符串求bit数

题意

给定字符串长度n，求敲好出现k个“bit”的字符串个数。

题解

反演或者容斥推导公式，推到公式后直接ntt优化即可。

2. 升级道具

公式推导和分治ntt， 一道期望题

题意

一个道具需要升级，成功升级的概率为$p_i$,升级失败并且下降$j(1\le j\le i)$级的概率是$(1-p_i)\frac{w_j}{{\sum }_{k=1}^i{w}_k}$,求升级到n级的期望。

题解

首先根据期望推导公式，得到$E_{i+1}=\frac{E_i-c_i-\frac{\left(1-p_i\right)}{{\sum }_{j=1}^i{w}_j}\cdot \left({\sum }_{j=1}^i{w}_j\cdot E_{i-j}\right)}{p_i}$, 又由于不知道$E_0$,所以考虑使用$E_i=a_i\ast E_0+b_i$的形式替换原来的$E_i$，这样就能得到关于$a_i$和$b_i$的一个正确的表达式，而且知道初始值为$a_0=1,b_0=1$, 这个时候就能使用分治ntt进行优化了。

3. 泰勒展开和双元ntt

统计长度为𝑛且数位𝑖出现至少𝑐𝑖次的数字串数量

题意

询问长度为n的数字字符串，且每一个数位的出现次数最少为$c_i$次的构造方案数。n有1E7，${\sum }_0^w{c}_i\le 50000$

题解

由于n比较大，如果直接使用ntt进行卷积的话会超时，使用泰勒展开：$e^x=1+x+x^2/2!+x^3/3!+...+x^n/n!+Rn(x)$替换原始生成函数，得到：${\prod }_{k=0}^9\left(\exp x-{\sum }_{i=0}^{c_k-1}\frac{x^i}{i!}\right)$，可以将$\exp x$堪称一个元y，让后对于y的系数全部是一个多项式，通过暴力维护y的系数，通过ntt进行系数的合并，这样展开以后，对于每一个询问，可以便利每一个y的系数进行查找即可。

注意点：在使用快速乘的时候，会有一个log，最好使用数组提前预处理。如果处理数据比较大，可以使用逆元完成$a^{n-j}=\frac{a^n}{a_j}$对数据的记录。

4. 普通容斥，前缀和和分治ntt优化

长度为m, 长度为n的连续子序列不包含n的排列的数量

题意

构造长度为m的序列a$（a_i\le n）$，且所有长度为n的连续子序列都不是n的排列，求方案数量。

题解

考虑先计算从第i个位置开始出现排列，再容斥计算没有排列的数量。
设$f_i$表示$[i,i+n-1]$内是一个序列，序列总长度为$i+n-1$的排列数量，这样就可以通过普通容斥求出总的没有排列的序列数量。
那么如何求出$f_i$呢？我们可以推导出公式:
$$f_i=n^{i-1}n!-\sum _{j=i-n+1}^{i-1}{f}_j\ast (i-j)!-\sum _{j=1}^{i-n}{f}_j\ast n^{i-j-n+1}$$
对于这个式子，可以先考虑初始化所有$f_i=n^{i-1}n!$，然后通过分治ntt的时候分别维护前缀和$f_j\ast n^{-j}$和使用ntt求解 ${\sum }_{j=i-n+1}^{i-1}{f}_j\ast (i-j)!$,这样就可以得到一个复杂度为$O(nlo{g}^{2}n)$的做法。但是好像总是超时额~~

5. 关于区间长度的公式转化成fft，利用fft进行优化

https://codeforces.com/gym/103855/problem/G
。。。待更新

期望类

1. 树上无向边变有向边，求走到根的期望

树上期望和区间组合数学，一道期望和组合题，角度：边。无向边变成有向边的贡献

题意

给定一个树，随机将k条边变成指向1的有向边，求从起点s到1的走过的边数期望，在每个节点走向的下一条边的概率相等。

题解

一个常用结论：每个结点走到父节点的期望值等于该子树的大小*2-1。
而将一条无向边变成有向边对于这条有向边连接的子树而言没有任何影响，对于所连接的父亲而言，相当于删除了改边。
从边的角度考虑处理每条边对期望的贡献，首先考虑这条边对所有必过点的贡献，发现贡献都是该子树大小乘以2。而每个边贡献的概率只与其到必过点的距离有关，所以可以使用深度来对距离进行统计，使用区间加减的思路优化时间复杂度。

组合数学

1. 一道生成序列求原排列的问题

两两配对的序列 + 确定先后顺序 + 卡特兰数。从角度找一个充分必要的条件

题意

给定一个n$(1\le n\le 5E5)$，构造一个长度为2n的排列满足该序列可以生成两个长度为n且元素不重复的序列A、B，这两个序列对应位置相乘的乘积最大，求这样的原序列有多少个。

题解

首先每个数都是成对的。对于一个存在这样划分的序列来说，一个必要条件是每一个对都有一个先后的顺序，并且对内也有一个先后的顺序。如果确定了每对的先后顺序和每对的内部顺序的话，那么便一定存在这样的一个生成序列，所以这是一个充分必要的条件。然后在这个推导的基础上，取出每一对的第一个数，再取出每一对的第二个数，发现一个必要条件是每对的第一个数的数量再每个位置一定要比第二个数的数量多，且最后数量相同，这就相当于一个括号匹配数量的问题，然后发现满足这个条件就一定能够满足外部和内部的先后顺序，这是一个充分必要的转化。那么使用卡特兰数就可以求出所有的可能。

各种反演

1. 关于gcd的反演

一个转化成gcd，在提取d，在进行反演的题目

题意

$f(n)={\prod }_{i=1}^m{p}_i^{a_i\%2}$，给定了$b_i$，求$\left({\sum }_{1\le i<j\le n}f\left(b_i\times b_j\right)\right)\mathrm{mod}\left(10^9+7\right)$

题解

纯纯的反演题，首先拆开$f(b_i\ast b_j)$，转化成带有gcd的简单单变量形式，然后提取d，通过莫反对公式进行转化，通过多次复杂度为调和级数的预处理最终求出结果。

2. 关于欧拉函数和gcd的运用

gcd的转化，欧拉函数

题意

$a+b+c=n$，求$\sum lcm(c,gcd(a,b))$

题解

考虑暴力枚举c，求出所有的可能gcd的贡献。对于每个gcd，满足的条件是$a+b=n-c,gcd(a,b)=d$，根据gcd的性质，知道$gcd(a,b)|(n-c)$，由此可以推断出$gcd(a/d,,b/d)=1,a/d+b/d=(n-c)/d$,即$gcd(a/d,,(n-c)/d)=1,a/d+b/d=(n-c)/d$，满足这样条件的贡献是$\varphi ((n-c)/d)$，所以就可以在O(nlogn)内求出答案。

结论

${\sum }_{a+b=n}[gcd(a,b)=d]=\varphi (n/d)$

整除分块

1. 题目链接

一道min25但是可以用杜教筛卡过的题

题意

$n,m\le 1E9$，求在长度不超过n，最大值不超过m，且后一个数为前一个数的倍数的序列个数。

题解

别人一看min25 筛，我第一眼看一脸懵逼。
首先使用 除分 提取出所有的阶梯倍数，然后求所有不相等的阶梯倍数不超过m的方案数，那么这个长度最多为30。
设$d{p}_{i,j}$表示长度为i最大值不超过j的方案数量，于是有公式：$d{p}_{i,j}={\sum }_{k=2}^{j}d{p}_{i-1,\lfloor j/k\rfloor }$, 看到这个公式，类似于杜教筛可以筛出每个长度为i长度不超过m的数量，然后使用组合数计算即可。
有三个地方需要注意，对于求组合数，由于该题长度很小，所以通过组合公式，可以在很短时间内求出组合数。
还有就是对于整除分块，从前往后使用差分递推的复杂度是$O(nlogn)$的，但是从后往前使用除数区间的复杂度却是$n\sqrt{n}$的，所以在杜教筛的时候，初始化前面的部分使用枚举倍数进行初始化。
另外就是初始化的时候如果独立就尽量放在外面，减少时间的占用。

1. 简单的公式分块

首先结论，在推到的公式中，有下取整，直接整数分块

题意

当前精神为s，喝一杯咖啡可以持续精神为当前精神c分钟，不能在咖啡药效阶段使用咖啡，咖啡药效过后减少（c+1）的精神，如果没有和咖啡，每分钟损失1的精神。当精神减少到0及一下的时候死亡。问存活的最长时间。

题解

首先，打表发现到后面都要使用咖啡，或者观察发现，或者证明：如果从某个时刻开始喝咖啡，则此后喝咖啡是必然不间断的。。证明如下：如果在第一次喝咖啡后存在某个时刻体力值为 𝑖 ，可以喝咖啡却没有喝，则必然可以将体力值为 𝑖 之前的第一次喝咖啡时刻推迟到 𝑖 而其他喝咖啡时刻不变，这样调整后总完成度一定会变好。
关键词：顺序，前后谁更优，贪心。
然后枚举开始使用咖啡的时候，会得到一个带有下取整的公式，可以使用简单分块进行优化。

容斥

1. 子矩阵gcd之和

矩阵求所有子矩阵的gcd之和

题意

给定一个大小为$n\ast m$的矩阵，矩阵内填有$1-n\ast m$的排列，求所有子矩阵的gcd之和。

题解

由于求每个子矩阵的花费太大，换一个角度，求每一个gcd值的贡献，但是求gcd恰好为x的矩个数太难了，但是求所有$x|gcd$的个数比较简单, 可以枚举每个x求出所有子矩阵的gcd满足$x|gcd$的子矩阵个数。
求解全1子矩阵的个数是一个经典问题，在只能枚举每个为1的点的情况下，考虑以该点为右小角的矩阵个数，并通过对细节进行处理从而求解。

2. 相差为r的套娃

题目大意
有 𝑛 个套娃，现在要将这些套娃分成 𝑘 组，每组套娃按照大小排序后相邻两个套娃之间的大小差距要求 ≥ 𝑟 ，求方案数。

待写。。

3. 数论+莫比乌斯容斥+多项式乘法的理解

$gcd\le q,lcm\ge p,1\le a_i\le m,m\le 1E5,n\le 1E9$的方案数

题意

给定$(1\le p,q,m\le 1E5,n\le 1E9)$,求满足$(gcd\le q,lcm\ge p,1\le a_i\le m,m\le 1E5,n\le 1E9)$的所有方案贡献，对于每个方案的贡献是：$\prod a_i$。求出所有方案的贡献和。

题解

我们要求$(gcd\le q,lcm\ge p)$, 由于对于情况$(gcd\le q,lcm\le p)$和$(gcd\ge q)$更加好求解方案数量，所以可以通过容斥来求，先求出总的个数，然后减去其他情况的个数即可。
对于情况$(gcd\ge q)$，可以直接用莫比乌斯容斥求出。
对于情况$(gcd\le q,lcm\le p)$， 如果固定gcd，那么就相当于求解问题$gcd=1,lcm\le p$,枚举每一个lcm就相当于求$gcd=1,lcm=i$的贡献的和，这可以发现对于每个lcm的质因子p，$p^0,p^{mx}$一定至少要出现一次，这里也可以通过容斥求出来，然后直接乘起来就可以了(多项式乘法分解的理解)

4. 普通容斥和二项式容斥， 对普通容斥的进一步理解，多项式的理解

普通容斥

题意

给定$n,m,k$, 构造长度为n的01字符串，其中最长的连续1的串的长度是k，1的个数是m，问这样串的个数有多少个。

trick

将条件进行公式化，稳定化，比如确定每个零之间的1的个数为$x_i$。
有时候普通容斥和二项式容斥都能解决当前问题，但是对不不同目标和角度，两者的复杂度相差较大。
普通容斥首先需要找到划分集合的条件因素,然后就好做了。

题解

关键转化：设每个0之间的1的个数为$x_i$，那么可以获得条件为${\sum }_0^n{x}_i=m$并且$0\le x_i\le k$且存在$x_i=k$。
根据前缀和知道对于$x_i=k$的条件可以通过前缀和相减得到。所以只需要求解${\sum }_0^n{x}_i=m$并且$0\le x_i\le k$的条件，根据减法原理，只需要考虑求取所有存在$x_i>k$的情况，按照条件$x_i>k$划分出n个集合，求出这些集合的并集即可，由于求取有j个$x_i>k$的条件可以通过隔板法在$O(1)$内求出，所以可以在$O(n)$内容斥出结果。所以从而可以求解。
还有一种解法就是考虑每个$x_i$的生成函数$f(x)$，就相当于求$[x^m]f(i{)}^n$, 这个可以用ntt和快速幂在$O(nlognlogn)$内求出。也可以过。。

概率题

1. 忽视没有用的选择，延伸某些可能性的可能数量

题目链接

炉石传说

题意

有两个阵营，每个阵营分别有一个英雄和7个随从。每次从两个阵营中随机选择一个人进行攻击，降低10生命值。一个阵营胜利当且仅当当前阵营英雄没有死亡且对方阵营英雄已经死亡的情况下发生。给定每个阵营的每个人的生命值，求第一个阵营获胜的概率。

题解

首先发现阵营的胜负与随从没有任何关系，所以可以不考虑攻击随从的情况。在只考虑两方英雄承受攻击的情况下，设第一个英雄承受攻击次数为$x$，第二个英雄承受攻击次数为$y$，那么采用公式$p=\frac{胜利的可能数}{所有可能数}$,只不过对于每个胜利的可能数要乘以贡献值，可以得到公式$p=\frac{{\sum }_{k=y}^{x+y-1}\left(\genfrac{}{}{0ex}{}{k-1}{y-1}\right)\ast 2^{x+y-1-k}}{2^{x+y-1}}$。或者使用公式$p=\sum (所有赢的情况概率)$也可以求出公式$p={\sum }_{k=y}^{x+y-1}\frac{\left(\genfrac{}{}{0ex}{}{k-1}{y-1}\right)}{2^k}$。

公式

1. 去绝对值，复杂度溢出

题目链接

两个数组中是否存在差值相等

题意

给定两个长度分别为n和m的数组A、B，询问是否存在$i,j(1\le i,j\le n)$和$k,l(1\le k,l\le m)$满足$|a_i-a_j|=|b_k-b_l|$，如果存在输出满足条件的任意的$i,j,k,l$，如果不存在，输出$-1$。$(1\le a_i,b_i\le 1E7)$

题解

对条件进行化简可以得到：$a_i+b_k=a_j+b_l$，而所有的$a_i+b_k$最多只有2E7种状态，所以可以直接暴力记录即可。对于重复地特殊情况分开讨论即可。
易错：由于对于重复地数我是用continue进行去重，这导致每次并不能都更新cnt数组，导致复杂度不确定性，所以需要使用unique进行去重。

2. 公式的递增和递减

题目链接

平方距离对称抽越远，递增变化越快

题意

一个有1E5个点的图，有1E5左右的带权边，在任一点u时，可以花费$(u-v{)}^2$传送到v点，传送次数不能超过k$（0\le k\le 20）$，求从1点出发到每一个点的最短权重。

题解

看见平方，距离越远，递增越快。对于一次飞跃而言，可以通过分治来求得飞跃后的最短距离，并通过迪杰斯特拉即可求解。
距离越远越不可能，可以考虑使用双分治来实现。

3. 加减乘除，公式推导，单调分析

题目链接

两种价值，求最大的分配

题意

给定n个物品，每个物品有两个价值，询问：给定a、b, 求x，y，满足$a\ast x+b\ast y=n$，使在n个物品中，选择x个第一个价值，选择y个第二价值，最终的总价值最大。

题解

每个物品有两个价值，那么可不可以先确定每个物品第一个价值选了0~1的所有情况。通过先选所有的第一个价值，然后再替换成第二个价值，相当于作一个减法，然后对所有的差值进行排序，就可以找到选x个第一个价值，y个第二个价值所有的情况。 对于每次询问，发现总价值是关于x先递增，再递减的，那么可以确定所选x一定再最大值所在x的左右两端，通过公式推导就可以在$O(1)$内算出结果。

周期

1. 裴蜀定理和T2= xT1之间的联系

题目链接

每次走k步，走n次，多次修改并询问如何使经过的值最大

题意

在一个长度为n的序列上任意选择从s开始，每次走k步，总共走n次，获得的价值为每次所在位置的数值和，求所有走法的可能的最大值。q次修改，每次修改一个位置上得数字，求每次修改后的最大值。

题解

首先由裴蜀定理可以知道k至于n的所有因子有关，又对于不同的k分析所有的s可以知道对于$k1=x\ast k2,k1|n,k2|n$,k1肯定更加优秀，因为对于k1中的最大值，k2一定可以选择更多的一半k1从而做出更多的贡献，所以只需要考虑所有的$\frac{n}{p}$即可,其中p为n的质因子。这里可以直接用multiset和数组暴力计算和存储即可。由于一个数的质因子最多为6个，所以暴力不会超时。

取模

1. 莫比乌斯数+同余条件+分治判断

题目链接

判断一个字符串是否是1-1E9莫比乌斯数的绝对值字符串的一部分

题意

对于1-1E9的莫比乌斯数的绝对值连接成的字符串，现在给定一个长度为200的字符串，需要判断该字符串是否是莫比乌斯串的子串。

trick

如何判断1E9内的是不是莫比乌斯函数，很容易知道一个莫比乌斯数肯定存在一个质数的平方作为因数，由于$p^2\le 1E9$,所以筛出所有$1\le p\le \sqrt{1E9}$，可以对每个质数进行判断即可。但是这样对于一个数判断的时间复杂度是$O(\sqrt{n})$的。
可以通过因子和倍数的角度进行分支，对于小因子$a$，枚举该数是否存满足$a|n$, 对于大因子，首先预处理出所有的大因子的倍数，然后判断该数是否在这个倍数里面就可以了，这个部分可以使用unordered_map来完成。

题解

在使用上面trick的条件下，我们可以在时间复杂度为$O(200)$下判断一个起点是否满足。那么如何枚举这个起点呢？
可以知道在200长度限制下，设起点为$x$，那么对于每个$p^2\le 200$，在这些数的倍数上必须满足所有的位置都必须是0，利用这个必要条件可以枚举条件，满足某个同余条件，那么枚举所有同余条件的可能，可以得到一个条件$x\%(2^2\ast 3^2\ast 5^2\ast 7^2\ast 11^2\ast 13^2)=y$的一个条件，由于模数比较打，这个在$1E9$范围内只需要枚举两个数就好了。
那么共有多少个同余条件呢， 对于每个$p^2$，如果0比较多的情况下，肯定情况非常多的。那么考虑如何限制0的个数，可以计算知道，在$p^2$都不重复的情况下，最多可以存在104个1，也就是说1的个数至少也是96个，在这个限制条件下，由于是乘积的形式，可以感受到递减的速度非常快，复杂度呈指数级递减，大概总体复杂度在O(1E8)，需要精心的实现才能够通过。

一些小trick：

1. 求互质的数的个数，在用容斥枚举质数集合的时候，使用dfs进行枚举，不经可以剪枝，而且还少了一个n的复杂度。
2. 一些复杂度看似是对的，但是continue增加了这种不确定性，最好能够直接跳或者unique。