有 n 个不可取分的 k 面骰子,对于每个,求有多少种方案使得:任意两个骰子朝上的面要么相同,要么和不为.答案对取模.
先枚举.也就是说,,......不能同时出现.直接枚举有多少组里出现了一个.假设有组.设这个有种选择(左边或者右边).然后考虑出现了多少次:,其中.然后枚举表示比大的数字出现的次数.把放在一起插版即可.
设表示 x 这个礼物第一次得到的时间.要求.考虑容斥.
定下来:直接算随到一个的概率.假设有个 pair 满足,一共有个 pair.那么期望就是.
考虑 DP.表示现在考虑第行第个格子,表示每行最后一个元素选不选.考虑是否在子集中.
考虑容斥.枚举表示出现次数小于等于.其中表示出现次数小于等于 1 的方案数.
考虑枚举有个集合含有中至少一个,其他集合则不含有.
显然不含有的子集族数为.
对于这个个集合,我们考虑把分入个集合,有的数字可以不放,每个数字最多出现一次.相当于再拿一个集合出来装垃圾.我们给垃圾堆强制加入数字来保证每个集合非空.同时我们认为所在的集合指向垃圾堆.这样就相当于是个数分成个非空集合,那么方案数就是.
至于这个集合的其他数字则可以任意填,并且由于个集合各种含有不同的的数字,因此其他部分就不需要考虑重复的问题了,那么方案数就是.
题意:给你一个 n 个点的数,其中 n 是偶数.问有多少种将个点配成对的方式,使得每对点的路径并覆盖了整棵树.
不合法的情况就是某条边不被经过,相当于这条边被割掉.因此考虑容斥.暴力的做法是枚举被割掉的边集,然后每个连通块内无限制连边的方案数,复杂度.
那么考虑 DP 计算容斥贡献.设表示的子树中,所在连通块大小为,被割的边数的奇偶性为的配对方案数.注意,我们只统计被割掉的连通块的配对方案数,所在的连通块暂不统计配对方案数.
不割.相当于把所在的连通块接在所在的连通块上.则和可以贡献到上.
枚举的子集.要求中的所有集合都满足最小值在中,问方案数.记作.答案就是.
从大到小考虑 A 中的元素.表示的最小值属于 A.
用另一个反转公式,那么如果的定义式成立,那么成立.这样就证完了.
给定 n 个结点的树,从某个点出发开始随机游走:在点 u 时,有的概率留在原地,否则等概率向相邻结点移动,直到移动到 1 号点停下.求从每个结点出发直指停下,所花费的时间的 k 次方的期望.
设到根结点的期望时间是.我们要求.
考虑按照从小到大的顺序做.设:
可以按树上高消的套路做了.要记得预处理斯特林数.
设连通块数为 T:.问题转化为求出,它表示选出了个连通块.
设表示 n 个点 t 个连通块的图的个数.
在一个 s 个点的图中,存在 s-n 条边,使图中形成了 n 个连通块,第 i 个连通块中有个点.
现在我们需要再连接 n-1 条边,使得该图变成一棵树.对于一种连边方案,设原图中第个连通块连出了条边,那么这棵树的价值为:
求出所有可能的生成树的价值之和,对取模.
那么复合函数求导得到(sum 里是个复合函数)
题意:给出无向图 G,对边染 K 种颜色之一.一个环上面的边旋转后得到的染色方案视为相同,求不同的染色方案数.
求出所有的点双(每个点双是独立的):
复合环:可以交换两条边的颜色.只用统计不同颜色出现次数的方案数.插板.