---

title: 杂记

---

。。放一些公式来帮助回忆什么的。。

基础知识

$$\begin{eqnarray*} e^x & =& \sum^\infty 1 + \frac{(e^x)'(0)x}{1!} +\frac{(e^x)''(0)x^2}{2!} +\frac{(e^x)^{(3)}(0)x^3}{3!} \dots \\ &= & 1 + \sum_{i = 1}^\infty \frac{x^i}{i!}= \sum_{i = 0}^\infty \frac{x^i}{i!}\\ \end{eqnarray*}$$
在指数上变一变可以当扰动项，例如用来去掉奇偶项什么的。
只要记住指数控制的是自变量就行了
$$\begin{eqnarray*} e^{-x} &= & \sum_{i = 0}^\infty (-1)^k\frac{x^i}{i!}\\ e^{17x} &= & \sum_{i = 0}^\infty \frac{17^ix^i}{i!} \end{eqnarray*}$$

$$\begin{eqnarray*} \ln(1 - x)&=&\sum^{\infty} 0 + \frac{(\ln(1 - x))'(0)x}{1!} +\frac{(\ln(1 - x))''(0)x^2}{2!} +\frac{(\ln(1 - x))^{(3)}(0)x^3}{3!} +\dots \\ & = & \sum^{\infty} 0 + \frac{1}{1!}\times \frac{x}{x_0 - 1} + \frac{-1}{2!}\times\frac{x^2}{(x_0 - 1)^2}+\frac{-1\times -2}{3!}\frac{x^3}{(x_0 - 1)^3} + \frac{-1\times -2\times -3}{4!}\frac{x^4}{(x_0 - 1)^4}+\dots\\ & = &\sum^{\infty}0+\frac{1}{1!}·\frac{x}{-1} + \frac{(-1)·1!}{2!}·\frac{x^2}{(-1)^2}+\frac{(-1)^2·2!}{3!}·\frac{x^3}{(-1)^3} + \frac{(-1)^3·3!}{4!}·\frac{x^4}{(-1)^4}+\dots\\ &=&\sum^{\infty}0+\frac{(-1)^{2i - 1}·(i - 1)!·x^i}{i!}\\ &=&0-\sum^{\infty}_{i \geqslant 1}\frac{x^i}{i} = -\sum^{\infty}_{i \geqslant 1}\frac{x^i}{i} \end{eqnarray*}$$

$$加法就是变了个号\\ \ln(1+x) =\sum^{\infty}_{i \geqslant 1}(-1)^{i - 1}\frac{x^i}{i}\\ $$

生成函数

EGF在算有标号集合的时候，实际上是不停给对象去标号然后再标号。

Exponential Formula

形式幂级数与麦克劳林级数的复合

$$e^{A(x)} = \sum_{i = 0}^\infty \frac{A(x)^i}{i!}\\ 底下的阶乘是在给选取的i个A(x)去重$$

形式导数、积分、对数函数

对形式幂级数取Ln的时候A(x)常数项必须是1.

对其求Exp的时候常数项必须是0，这可以用牛迭的式子记。

Exp：$\ln F(x) -A(x)\equiv0$

Bell Polynomial

很不幸，这一部分我全忘了= =

OGF

。。。化式子的话。。。

$$差分\\ {\{1\}}^{\infty}_0\leftarrow \sum x^i=\frac{1}{1 - x}\\ $$

$$继续差分\\ s_n = \sum^n f_i,设\{f_n\}^\infty_0 = F(x)\\ \{s_n\}^\infty_0 \leftarrow\frac{F(x)}{1 - x}\\ $$

这符号打得我要疯了。。。。。直接用大小写区分数列和该数列的OGF好了= =。。。

$$对自变量做手脚\\ \sum m^kx^k = \frac{1}{1 - mx}\\ \sum m^{k}x^{ck} = \frac{1}{1 - mx^c}\\ 截取前缀后缀\\ \sum^5_{i = 0}x^i = \frac{1 - x^5}{1 - x}\\ 有了前缀那直接一减就行了\\ \sum_{i = 6}^\infty x^i =\frac{x^{5}}{1 - x}\\ $$

$$\frac{1}{(1 - x)^n} = \sum_{i = 0}^\infty {i + n - 1 \choose n - 1}x^i\\ 同时也是广义二项式定理的一个解释$$
来个总结的式子吧：

这其实给做题的时候化式子的方向指明了一个路，因为x的系数是不好处理的。。。如果不是某东西的次幂的话往往只有同一个数/前缀和才好差分，所以尽量往这边化。

EGF

关于EGF的恒等式除了Exponential Formula之外好像也不太清楚了= =。。。

关于它的一些式子变换还没有研究。。。先再说吧，反正目前来说知道那点组合意义也能应付些题了。

OGF平移的方法是乘/除以一个x，EGF向左平移一次的方法是乘一个n并除以一个x，然后你发现这是求导（惊不惊喜！）

杂项

玩游戏

这个题里面其中一步是要求$F(x) = \sum_{i = 1}^n\frac{1}{(1 - a_ix)}$
怎么求呢/kk这个1/x的形式看起来好眼熟啊

$$F(x) = \sum_{i = 1}^n\ln'(1 - a_ix)$$

发现。。。。。。。没有卵用。。。。

那先不求了，求一个好求的

$$\begin{eqnarray*} G(x) &=& \sum_{i = 1}^n\frac{-a_i}{(1 - a_ix)} \\&=&\sum_{i = 1}^n(\ln(1 - a_ix))' \\&=&\left(\ln\left(\prod_{i = 1}^n(1 - a_ix)\right)\right)' \end{eqnarray*}$$
辣么我们惊奇地发现！
$$F(x) = -xG(x)+n$$
哇！

英国之王

这种题一般是求出单个的贡献然后乘上方案数。。

重点在求单棵环套树的方案数上，没什么推式子上的亮点。。要注意的就是看到除以k想到求ln就行了= =

然后$\text{w}\times \text{h}$ solution里写的那个求环套树的方案的方法感觉很喵！！！

http://zhengruioi.com/download.php?type=tutorial&id=656

自然数幂求和

另外它还可以直接拉格朗日插值

扰动法

$$\begin{eqnarray*} S_k(n) + (n+1)^k &=& \sum_{i = 1}^{n + 1}i^k=\sum_{i = 0}^{n}(i +1)^k \\&=&\sum_{d = 0}^k\sum_{i = 0}^{n}{k \choose d}i^d=\sum_{d = 0}^k{k \choose d}S_d(n) \\ (n+1)^k &=&\sum_{d = 0}^{k - 1}{k \choose d}S_d(n) \\ (n+1)^{k+1} &=&\sum_{d = 0}^{k-1 }{k+1 \choose d}S_d(n) \\(k+1)S_k(n) &=& (n+1)^{k+1} - \sum_{d = 0}^{k - 1}{k +1\choose d}S_d(n) \end{eqnarray*}$$

现在我们可以用$O(k^2)$的时间来计算出对于同一个n不同k的答案。

斯特林数

升降幂转通常幂

$$\because x^{\overline{n}} = \prod_{i = 0}^{n - 1}(x + i)\\ \therefore x^{\overline{n}} = \sum_{k = 0}^n \left[ \begin{matrix}n\\k\end{matrix} \right]x^k\\\\ $$

由于下降幂只是变了个符号（每次k不变的时候才会乘一个-1）

$$x^{\underline{n}}=\sum_{k = 0}^{n}(-1)^{n - k} \left[ \begin{matrix}n\\k\end{matrix} \right]x^k$$

一般这个式子会在大力维护组合数的多项式的时候用到。

通常幂转升降幂

$$x^n = \sum_{k = 0}^n {n \brace k}x^{\underline{k}}$$

这个可以从组合意义解释。给n个球染上x种颜色的方法 = 枚举每种颜色的集合并给每种集合染色。

关于下降幂的形式肯定也有，但是我没查到，yy了一下感觉应该长这样。

$$x^n = \sum_{k = 0}^n(-1)^k{n\brace k}x^{\overline{k}}$$

快速求一行斯特林数

。。。。第一类斯特林数先咸鱼log方吧。。。。。我还不会一个log的。

两个log直接$x^{\overline{n}}\prod_{i = 1}^{n }(x + i + 1)\\$ 就行了。

第二类斯特林数比较好求，顺着容斥的式子推一下就行了。有一个问题事斯特林数的盒子之间是没有区别的，那么我们可以先给盒子标号，然后再去标号就好了。枚举有哪些盒子是空的

$${n \brace m} = \frac{1}{m!}\sum_{k = 0}^m (-1)^k{m \choose k}(m - k)^n\\ 拆一下组合数就是卷积了$$

自然数幂求和

值得说一下的是那个离散微积分的部分。下面这张图来自MoebiusMeow的Blog

$$\begin{eqnarray*} S_k(n) &=&\sum_{i = 1}^{n}\sum_{d = 0}^k{k \brace d}i^{\underline{d}} \\&=&\sum_{d = 0}^k{k \brace d}\sum_{i = 1}^{n}i^{\underline{d}} \\&=&\sum_{d = 0}^k{k \brace d}\sideset{}{_0^{n+1}}\sum x^\underline{d}\delta x \\&=&\sum_{d = 0}^k{k \brace d}\left.\frac{x^\underline{d+1}}{d+1}\right|_0^{n+1} \\S_k(n)&=&\sum_{d = 0}^k{k \brace d}\frac{(n+1)^\underline{d+1}}{d+1} \end{eqnarray*}$$
到这里，预处理出斯特林数后已经可以O(k)求出一组(n, k)了。

并且可以发现，$S_k(n)$ 是一个关于n的k+1次多项式。

$$\begin{eqnarray*} \\S_k(n)&=&\sum_{d = 0}^k{k \brace d}\frac{(n+1)^\underline{d+1}}{d+1} \\&=&\sum_{d = 0}^k{k \brace d}\frac{1}{d+1}\sum_{i = 0}^{d+1}(-1)^{d +1- i}\left[\begin{matrix}d+1\\i\end{matrix} \right](n+1)^i\\ S_k(n)& =&n^k+\sum_{i = 0}^k\sum_{d = i}^{k+1}{k \brace d}\left[\begin{matrix}d+1\\i\end{matrix} \right]\frac{(-1)^{d +1-i}}{d+1}n^i\\ [n^i]S_k(n)& =&\sum_{d = i}^{k+1}{k \brace d}\left[\begin{matrix}d+1\\i\end{matrix} \right]\frac{(-1)^{d +1-i}}{d+1}+[i == k] \end{eqnarray*}$$

于是可以用k方的时间求出每一项的系数。

所以无论是求一行还是求一列，我们都能用k方的时间来求出。

不相交集合并卷积

问题：求

$$\sum_{s\subseteq S}f_sg_{S -s}$$
我们知道普通的or卷积是通过
$$[A\cup C =C]\cap[B\cup C =C] \Leftrightarrow[(A\cup B)\cup C = C]$$
这一点来造DFT的。具体步骤就是先求$f$的超集合变换，求$g$的超集合变换然后点乘求出$t$的超集合变换，最后再把$\hat t$逆变换回来。

那么在处理的时候，问题的限制可以转化为

$$[A\cup B = C]\cap[A\cap B= \emptyset] = [A\cup B = C]\cap[|A|+ |B| = |C|]$$
于是只要多加一维集合大小限制就行了，大致流程是：

对于所有sf,sg f[|sf|][sf] = g[|sg|][sg] = cnt
枚举长度i : [0, n]
    DFT(f[i], 0), DFT(g[i], 0)
枚举状态s : [0, 2^n]
    固定第二维s然后对长度那维做卷积。实际上就是f_s*g_s，只不过由于这里f_s,g_s都是多项式才要卷积的。
枚举长度i : [0, n]
    DFT(f[i], 1), DFT(g[i], 1)

hmmm，你发现这东西还可以求逆。

就是。。。它中间的卷积是个普通的加法卷积，所以直接暴力多项式求逆就行了。

比如你现在有了两个集合幂级数$f, t$并且已知$f*g=t$，那么求$g$的问题：

把f和t的变换都变换好。
枚举状态s
    Mult(t[s], Inv(f[s]));// 这里是普通的多项式求逆和多项式乘法
然后把t逆变换回来就是t了。

无论是求子集卷积还是求逆都是$\text{O}(2^nn^2)$

子集卷积求逆例题

然而实际上常数很大。我$2^nn^2$跑不过同学的$3^n$，哭了

这题也可以$2^nn^2\log{n}$直接写分治FFT，不过yyf用事实证明跑不过去

组合数取合数模

在模数小n大的时候可以选择卢卡斯来解决。

模数大 n比较小

就。。。质因数分解然后CRT。。。

如何求$\bmod{p^k}$的话就，把数变成ap+c的形式来记。。。由于n比较小暴力乘过去就行了。。。

。。

常用的组合恒等式速查

。。。。。

资料袋

WIkipedia:Exponential_formula

康复计划#3 简单常用的几种计算自然数幂和的方法

generalization of binomial theorem

Commonly Used Taylor Series

Taylor/Maclaurin Series Calculator