[关闭]
@Shadyqwq 2019-03-30T08:46:50.000000Z 字数 5823 阅读 895

title: 杂记


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

基础知识


在指数上变一变可以当扰动项,例如用来去掉奇偶项什么的。
只要记住指数控制的是自变量就行了

生成函数

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

Exponential Formula

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

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

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

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

Exp:

Bell Polynomial

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

OGF

。。。化式子的话。。。

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

广

来个总结的式子吧:

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

EGF

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

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

OGF平移的方法是乘/除以一个x,EGF向左平移一次的方法是乘一个n并除以一个x,然后你发现这是求导(惊不惊喜!)

杂项

玩游戏

这个题里面其中一步是要求
怎么求呢/kk这个1/x的形式看起来好眼熟啊

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

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


辣么我们惊奇地发现!

哇!

英国之王

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

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

然后 solution里写的那个求环套树的方案的方法感觉很喵!!!

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

自然数幂求和

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

扰动法

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

斯特林数

升降幂转通常幂

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

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

通常幂转升降幂

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

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

快速求一行斯特林数

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

两个log直接 就行了。

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

自然数幂求和

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


到这里,预处理出斯特林数后已经可以O(k)求出一组(n, k)了。

并且可以发现, 是一个关于n的k+1次多项式。

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

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

不相交集合并卷积

问题:求


我们知道普通的or卷积是通过

这一点来造DFT的。具体步骤就是先求的超集合变换,求的超集合变换然后点乘求出的超集合变换,最后再把逆变换回来。

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


于是只要多加一维集合大小限制就行了,大致流程是:

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

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

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

比如你现在有了两个集合幂级数并且已知,那么求的问题:

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

无论是求子集卷积还是求逆都是

子集卷积求逆例题

然而实际上常数很大。我跑不过同学的,哭了

这题也可以直接写分治FFT,不过yyf用事实证明跑不过去

组合数取合数模

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

模数大 n比较小

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

如何求的话就,把数变成ap+c的形式来记。。。由于n比较小暴力乘过去就行了。。。

。。

常用的组合恒等式速查

。。。。。

资料袋

WIkipedia:Exponential_formula

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

generalization of binomial theorem

Commonly Used Taylor Series

Taylor/Maclaurin Series Calculator

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注