[整理]多项式/生成函数题目泛刷

摘要:
二项式反演是一个通用术语,该证明保留用于实践。这个通称显然是卷积,所以问题很容易解决。从生成函数的角度出发,我们考虑Logo中P5409的第一种斯特林数和列。众所周知,圆形排列的EGF是,因此EGF显然是(dfrac{(lnfrac1{1-x})^k}{k!2^kD_{n-k}),并且组合的意思是在偶排列之后剩余的位错。标题指示方案的总数,所以很明显,有(sumlimits_{k=0}^ndbinomnk^2k!标志P4233致命丸的注释的答案实际上是具有哈希总数的图的数量。众所周知,哈希存在的必要和充分条件是强连通性,我们需要计算强连通的锦标赛图的数目。标志P4091[HEOI2016/TJOI2016]总和是一个愚蠢的公式,没什么好说的。

洛谷P5408 第一类斯特林数·行

众所周知,第一类斯特林数可用于普通幂和上升幂之间的转换:(x^{overline{n}}=sumlimits_{i=0}^negin{bmatrix}n\iend{bmatrix}x^i),也就是说我们需要快速求上升幂。
考虑倍增,有 (x^{overline{2n}}=x^{overline{n}}(x+n)^{overline{2n}}),瓶颈在于后面的 ((x+n)^{overline{2n}})
如何转化呢?其实就是把 (x+n) 复合到一个函数 (f(x)) 中,我们把组合数展开,再将差卷积化为和卷积。设 (g(i)=i!a_i)(h(x)=dfrac{n^i}{i!}),再引入 (g') 作为 (g) 反转指数的结果,那么易见

[egin{aligned} f(x+n)&=sum_{j=0}^ndfrac{x^j}{j!}sum_{i=0}^{n-j}g(i+j)h(i)\ &=sum_{j=0}^ndfrac{x^j}{j!}sum_{i=0}^{n-j}g'(n-j-i)h(i)\ end{aligned} ]

上式平凡,略去代码。细节巨大多,请谨慎编写

洛谷P5395 第二类斯特林数·行

众所周知第二类斯特林数有通项 (egin{Bmatrix}n\mend{Bmatrix}=sumlimits_{i=0}^mdfrac{(-1)^{m-i}i^n}{i!(m-i)!}),这个公式可以用二项式反演证明:考虑 (n) 个元素放到 (m) 个集合中的方案数 (m^n),它等价于选出若干个非空集合再放入元素,也就是 (m^n=sumlimits_{i=0}^mm^{underline{i}}egin{Bmatrix}n\iend{Bmatrix}=sumlimits_{i=0}^mi!dbinom miegin{Bmatrix}n\iend{Bmatrix})
二项式反演即得通项,证明留作练习。
这个通项显然是一个卷积式,于是此题易解。

洛谷P5409 第一类斯特林数·列

我们从生成函数的角度考虑,众所周知圆排列(即 (k=1) 的情况)的 EGF 是 (lndfrac1{1-x}),所以 (egin{bmatrix}i\kend{bmatrix}) 的 EGF 显然为 (dfrac{(lnfrac1{1-x})^k}{k!}),于是此题易解。

洛谷P5396 第二类斯特林数·列

同上一道题的处理方式,(k=1) 时的 EGF 就是 (e^x-1),所以 (egin{Bmatrix}i\kend{Bmatrix}) 的 EGF 为 (dfrac{(e^x-1)^k}{k!})
注意此解为错解且可能被卡,但是正解看起来很麻烦作者懒得推,于是就先咕掉。

洛谷P2767 树的数量

开题一看是傻逼题,直接碾生成函数 (F=x(1+F)^m),那么它的复合逆 (G) 显然为 (dfrac{x}{(1+x)^m}),于是拉反一下就有 ([x^n]F=dfrac1n[x^{n-1}](1+x)^{nm}=dfrac{inom{nm}{n-1}}{n})

洛谷P4491 [HAOI2018]染色

看到恰好先容斥掉,设 (t(k))(k) 种颜色出现了至少 (s) 次的方案数,(f(k))(k) 种颜色出现了恰好 (s) 次的方案数,那么 (t(k)=sumlimits_{i=k}^ndbinom ikf(i)),二项式反演即得 (f(k)=sumlimits_{i=k}^n(-1)^{i-k}dbinom ikt(i))。而 (t(i)) 是很好求的,它等于 (dbinom{n}{is}dbinom midfrac{(is)!}{(s!)^i}(m-i)^{n-is}),组合意义是先钦定 (is) 个位置,选 (i) 种颜色,剩余颜色随便放。
运用 P5408 的套路,设 (g(k)=dfrac{(-1)^k}{k!},h(k)=k!t(k),h'(k)=h(n-k)),那么方案数就是 (dfrac1{k!}sumlimits_{i=0}^{n-k}g(i)h(n-k-i)),暴力卷即可。

洛谷P5219 无聊的水题 I

题目中出现了树计数和点的度数,我们很自然地转化成 Prüfer 序列,题目也就是问 (n) 个数排成长 (n-2) 的序列,出现次数最多的恰好出现了 (m-1) 次的方案数。
还是套路地将恰好容斥掉,考虑计数出现至多 (m-1) 次的减去至多 (m-2) 次的。
写出每个元素的 EGF:(F=sumlimits_{i=0}^{m-1}dfrac{x^i}{i!}),那么答案就是 ([x^{n-2}]F^n)

洛谷P4931 [MtOI2018]情侣?给我烧了!(加强版)

EI 为这题提供了一个极为巧妙的解法,整理如下(但是 EI 神仙的过程实在过于简洁,导致我卡了很长时间)
首先我们设 (D_{k})(k) 对情侣都不在一排的方案数,恰好 (k) 对在一排的方案数就是 (dbinom nk^2k!2^kD_{n-k}),组合意义是选 (k)(k) 对情侣排列后剩下的错排。
题目中提示了总方案数,那么显然有 (sumlimits_{k=0}^ndbinom nk^2k!2^kD_{n-k}=(2n)!)
组合数的平方是什么鬼?我们突然想到,由于 EGF 可以卷积出一个组合数,那么我弄一个跟 EGF 类似,只不过每一项带的是 (dfrac{1}{(i!)^2}) 的东西就可以卷出来组合数平方了。
于是变成了 (D(x)e^{2x}=dfrac1{sqrt{1-4x}})
稍微解释一下右边是怎么来的,EI 和很多人都把这里略了。现在我们要求 (sumlimits_idfrac{(2i)!}{(i!)^2}x^i=sumlimits_idbinom{2i}ix^i),由于 (dbinom{i-1/2}{i}=dfrac{inom{2i}i}{4^i})(容易计算得出),所以原式即为 (sumlimits_idbinom{i-1/2}{i}4^ix^i),运用上指标反转有 (sumlimits_i(-1)^idbinom{-1/2}{i}4^ix^i=(1-4x)^{-1/2})(这个式子据说还挺重要?)。
求导有 (D'(x)=dfrac{8x}{1-4x}D(x)),提取系数则有 (D_n=4n(n-1)D_{n-1}+8n(n-1)^2D_{n-2}),于是可以递推求解。

洛谷P4233 射命丸文的笔记

答案其实是哈路总数比上有哈路的图数。
竞赛图的哈路总数很好求:选 (n-1) 条边连成环,剩下的随便连,答案是 ((n-1)!2^{n(n-1)/2-n})
众所周知有哈路的充要条件是强连通(感性理解),我们需要统计强连通竞赛图的数量。
发现普通竞赛图的 EGF(设为 (F))很好求,考虑用强连通的(设为 (G))表示普通的。
由图论知识,一个竞赛图缩点后会变成一条链状的 DAG,边从前连到后。所以把普通竞赛图看成一排强连通竞赛图,有 (F=dfrac1{1-G}),所以 (G=1-dfrac1F)

洛谷P4091 [HEOI2016/TJOI2016]求和

傻逼推式子,没啥好说的。

[egin{aligned} sum_{i=0}^nsum_{j=0}^ij!2^jegin{Bmatrix}i\jend{Bmatrix}&=sum_{i=0}^nsum_{j=0}^nj!2^jegin{Bmatrix}i\jend{Bmatrix}\ &=sum_{i=0}^ni!2^isum_{j=0}^nsum_{k=0}^idfrac{(-1)^{i-k}k^j}{k!(i-k)}\ &=sum_{i=0}^ni!2^isum_{k=0}^idfrac{(-1)^{i-k}}{k!(i-k)}sum_{j=0}^nk^j end{aligned} ]

卷积的形式水落石出。
不过这题有些奇特的边界条件,写的时候需要注意。
EI 对此给出了一个线性做法,有空补。咕咕咕

洛谷P5748 集合划分计数

如果你熟知 Bell 数的 EGF 是 (e^{e^x-1}) 那就做完了,这里主要简述一下推导过程,以帮助像我一样没看过/记不住的人。
Bell 数是将 (n) 个数分成若干集合的方案数,平凡地我们有分成一个集合的方案数的 EGF:(e^x-1),那么根据 (exp) 的组合意义就有上式。

CF960G Bandit Blues

题目长得十分 dp,我们先写一个式子:(f_{i,j}) 表示放了 (i) 个数,有 (j) 个前缀最大值的方案数,枚举最小数的位置不难得到 (f_{i,j}=f_{i-1,j-1}+(i-1)f_{i-1,j}),对递推式敏感的人可能一眼就能看出它是第一类斯特林数。
而答案的计算也很简单:我们钦定全局最大值的位置,那么答案为 (sumlimits_{i=1}^{n-1}egin{bmatrix}i\a-1end{bmatrix}egin{bmatrix}n-i-1\b-1end{bmatrix}dbinom{n-1}{i}),之后按照第一类斯特林数·列的处理方式计算,或者再由组合意义推一步化为封闭形式 (egin{bmatrix}n-1\a+b-2end{bmatrix}dbinom{a+b-2}{a-1})
双倍经验洛谷 P4609。

洛谷P2791 幼儿园篮球题

先写出式子:(dfrac{sum_{i=0}^mdbinom{m}{i}dbinom{n-m}{k-i}i^L}{dbinom{n}{k}}),我们发现难点主要在分子,考虑如何快速计算。

[egin{aligned} &sum_{i=0}^mdbinom{m}{i}dbinom{n-m}{k-i}i^L\ =&sum_{i=0}^mdbinom{m}{i}dbinom{n-m}{k-i}sum_{j=0}^Legin{Bmatrix}L\jend{Bmatrix}dbinom{i}{j}j!\ =&sum_{j=0}^Legin{Bmatrix}L\jend{Bmatrix}j!sum_{i=0}^mdbinom{m}{i}dbinom{i}{j}dbinom{n-m}{k-i}\ =&sum_{j=0}^Legin{Bmatrix}L\jend{Bmatrix}dbinom{m}{j}j!sum_{i=0}^mdbinom{n-m}{k-i}dbinom{m-j}{i-j}\ =&sum_{j=0}^Legin{Bmatrix}L\jend{Bmatrix}dbinom{n-j}{k-j}dbinom{m}{j}j!\ end{aligned} ]

预处理第二类斯特林数就可以 (O(L)) 做了。

免责声明:文章转载自《[整理]多项式/生成函数题目泛刷》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇【转载】Android卡顿检测方案spring boot 2.x Path with "WEB-INF" or "META-INF"下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

VC6.0设置选项解读(转)

其实软件调试还是一个技术熟练过程,得慢慢自己总结,可以去搜索引擎查找一些相关的文章看看,下边是一篇关于VC6使用的小文章,贴出来大家看看: 大家可能一直在用VC开发软件,但是对于这个编译器却未必很了解。原因是多方面的。大多数情况下,我们只停留在“使用”它,而不会想去“了解”它。因为它只是一个工具,我们宁可把更多的精力放在C++语言和软件设计上。我们习惯于这...

C++静态库与动态库(比较透彻)

这次分享的宗旨是——让大家学会创建与使用静态库、动态库,知道静态库与动态库的区别,知道使用的时候如何选择。这里不深入介绍静态库、动态库的底层格式,内存布局等,有兴趣的同学,推荐一本书《程序员的自我修养——链接、装载与库》。 什么是库 库是写好的现有的,成熟的,可以复用的代码。现实中每个程序都要依赖很多基础的底层库,不可能每个人的代码都从零开始,因此库的存...

MySql生成随机数

【说明】 mysql生成随机数基层函数使用:RAND() 【函数】 FLOOR(x)返回小于x的最大整数值 RAND()返回0到1内的随机值 【举例】 SELECT FLOOR(RAND()*10); -----------生成随机个位整数...

转:将字符串或表达式直接转为C#可执行代码的办法

原文地址:http://blog.csdn.net/qwlovedzm/article/details/6292147 近日有个项目有不少的计算公式,而且要求能定制,如何能将字符串或表达式直接转为C#的可执行代码就好了。 经过从网上查阅资料,发现有一个开源的工具类,将它修改后改为如下效果: [c-sharp]view plaincopyprint?...

sql server 函数--rand() 生成整数的随机数

rand() 定义: 返回从0到1之间的随机浮点值。 举例说明: select rand() as 随机数   结果如图: select cast( floor(rand()*N) as int )  --方法1 结果:20 select cast( ceiling(rand()*N) as int ) --方法2 结果:43 大致一看,这两种方法没什么...

概率生成函数

part0 What is it ? 一类人为规定的函数 设 (f(i)) 为第 (i) 项的概率 那么设 (F(x)) 为 (f) 的生成函数 [F(x) = sum_{i geq 0} f(i) * x ^ i ] part1 一些性质 (1: F'(1) = E(x)) 假如第 (i) 项的值为 (i) 则这件事情的期望 (E) 为 [sum_...