竞赛讨论区 > 【博客】斯特林数、容斥和反演整理

【博客】斯特林数、容斥和反演整理

头像
fastle
编辑于 2019-04-26 21:56:54 APP内打开
赞 17 | 收藏 8 | 回复7 | 浏览1263

斯特林数

第一类斯特林数
  • s(n, m)表示将n个元素分成m个圆排列的方案数
  • 也可以记作
    递推式
  • 表示可以自己单独拿出来成为一个环, 也可以放在任意一个元素的前面
    性质1
  • 证明:每个排列实际上对应着一个置换
  • 考虑s(n,i)分成的i个环, 实际上就是对应着循环节个数为i的一种置换, 一一对应过去就是所有置换方案就是全排列了
  • 性质2
  • 证明:使用数学归纳法
  • 对于的情况, 显然成立
  • 对于的情况
  • 同理要证明
自然幂数和问题
  • 记录
  • 那么考虑
  • 把这个带进式子求得
  • 递推即可
    预处理方法
  • 分治fft
  • 构造第一类斯特林数生成函数
  • 显然可行
  • 倍增法
  • 那么存在
  • 递归求解F_n(x), 然后考虑快速求解
  • 考虑设
  • 后面显然可以卷积
    第二类斯特林数
  • S(n,m)表示把n个元素划分成m个子集的方案数
  • 记作
    递推式
  • 组合意义是放到任意一个集合中或者新建一个集合
    性质1
  • 可以看做进行容斥, 枚举多少个集合不放置, 其余的集合随便放置, 最后每一种情况会统计m!次
  • 显然可以卷积求解
    性质2
  • 证明:可以看作将n个求放到m个带标号的盒子内, 那么我们枚举哪些盒子不为空, 则

-

容斥

经典容斥系数的解
  • 证明每个地方只要被覆盖了就会被统计1次答案, 假如这个地方被覆盖了n次, 那么
    错排问题
  • 考虑枚举那些地方强制相同, 然后其余地方随便放置。
min-max容斥
  • 设S是一个可重集合,max(S)和min(S)分别表示集合中的最大值和最小值,则有如下式子成立:
  • 证明
  • 以第一个式子为例,设max(S)=x,那么只有T={x} 时的min(T) 为x(可能有多个相同的最大值,这时候随便钦点一个就可以了;
  • 对于除此之外的所有T,肯定至少存在一个集合A∩T = ?, 使得min(T和A每个子集的并)等于min(T),
  • 然后由于从A中选择奇数偶数个元素的方案数相同, 所以正负抵消, 最后只剩下了x
推广1
  • 在期望下该式子也是成立的, 即

反演

反演本质
  • 给定数列存在关系
  • 这里使用f推出了g, 那么我们反演的过程就是使用g推出f
  • 也就是找到系数数组b,使得
  • 引入克罗内克函数(为了好写)
  • 整合两个式子得到
  • 同理
  • 显然, 这里能够反演的前提条件是
二项式反演
  • 证明, 即要证明
  • 仅证第一个, 第二个类似
  • 后面这堆式子仅当n等于i的时候取值为1, 否则取值为0, 故得证
  • 另一种形式是
  • 证明
  • 得证
斯特林反演
  • 式子是
  • 需要证明
  • 首先容易得到
  • 那么
莫比乌斯反演
  • 式子是
  • 需要证明
  • 我们来证明
  • 首先n不是i倍数的时候答案一定是0
  • 假设n是i的倍数, 那么
  • 同理可证另一个

7条回帖

回帖
加载中...
回帖

近期热帖

等你来战

查看全部

热门推荐