题目大意 玩一场游戏，每一轮在 中随机生成一个整数 ，生成 的概率为 。若 不小于之前生成的任何数，则游戏继续并进入下一轮，否则游戏结束。假如说最后游戏共进行了 轮，则游戏的得分为 。求游戏分数的期望值 ，答案 输出。 输入为 个数 ，。 思路 游戏生成的数字序列一定是类似 ，即 的数字由小到大依次产生，每个数字出现的次数为 。 构造母函数 ，对于每一项 ，指数 表示数字 出现的次数， 就是 连续出现 次的概率。每一个数的出现次数都对应多项式 ，将这 个多项式进行卷积运算，即为 。卷积的结果为 ， 为生成序列的长度，系数 自然是生成长度为 的非递减序列的概率。仔细思考， 同时也是游戏进行轮次超...

题目大意 有一个棋盘只有两行，但有 列，第一行上有 个炮，第二行上有 个炮。 众所周知，中国象棋中炮吃一个子时需要中间有一棋子作为炮架。记发生 次炮吃炮事件的方案数 为 ，输出 。题目需要输出两个答案，分别对应两个限制条件：1.不考虑两行发生事件的顺序；2.事件必须先在第一行发生，之后再在第二行发生，不能再返回第一行发生。 思路 对于某一行上共 个炮，考虑哪一个炮作为炮架，产生一次炮吃炮事件的方案数为 ；因此，产生 次炮吃炮事件的方案数为 。 枚举 ，表示第一行发生 次炮吃炮事件，第二行发生 次炮吃炮事件。对于答案1，我们要从 次炮吃炮中选出 次在第一行中发生的，；对于答案2，先在第一行发生 ...

题目大意 给出多重数集 ，求其所有大小为 的子集的 之积。共 组数据，要求答案 输出。 不保证 中所有数各不相同，不保证 为质数。。 事后交题时感觉 。  思路 枚举所有可能出现的 ，设 的长度为 的子集个数为 ，那么最终答案 {%raw%}{%endraw%}。我们的任务是求出每一个 。 枚举 时，统计 中 的倍数出现的个数 ，从这 个中数字中选 个组成备选集合 ，共 中方案， 中所有数的 必然是 的倍数，从 个方案中去掉 的方案，剩下的方案数即为 。只要倒叙枚举 ，。 题目要求答案对 取模，考虑到 很大，我们要进行欧拉降幂。需要注意的是，当 ，也可直接用下面式子的第三条。  考虑到 很大，...

H. Hash Function 题目描述 For a given set , we called a hash function perfect hash function of , if it satisfies , .  Given a set S with non-negative integers, please find the minimum positive integer seed that function ​ is a perfect hash function of ​.  输入描述 The first line of input contains one intege...

题目描述 Given two arrays , with length , you should perform exactly operations in array .  For each operation, choose elements , (​) and swap the positions of and .  Please maximize . 输入描述 The first line of input contains two integers ( ,), describing the length of , and number of operations. The secon...