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

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

题目大意 给出多重数集 ，求其所有大小为 的子集的 之积。共 组数据，要求答案 输出。 不保证 中所有数各不相同，不保证 为质数。。 事后交题时感觉 。 思路 枚举所有可能出现的 ，设 的长度为 的子集个数为 ，那么最终答案 {%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 inte...

题目描述 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. Th...

题目描述   Today, ZLZX has a mysterious case, Orange lost his down jacket hanging in his dorm room. Under the expectations of everyone, detective Groundhog took his small spoon of the artifact and started the journey to solve the case.  After an in-depth investigation of the northernmost mysterious room...

题目描述   Groundhog took a math class. In this class, his math teacher said, any positive integer can be represented by the power of . For example, .  And powers are expressed in parentheses. That is, stands for . Therefore, can be expressed as .  Further more,for is expressed with , ,137 can be fin...

题目描述   Apollo is playing an interesting computer game. There are rounds in the game.  At each round, the computer will give Apollo two integers and , and Apollo can do exactly one of the following three actions.  Apollo can do nothing.  If integer has not been selected in all previous rounds, Apo...

题目描述   The following rules define a kind of integer tuple - the Legend Tuple:   is always a Legend Tuple, where k is an integer.  if is a Legend Tuple, is also a Legend Tuple.  if is a Legend Tuple, is also a Legend Tuple.  We want to know the number of the Legend Tuples where , .  In order to ...

题目描述   McDonald Thumb, the greatest president ever in the history of the Great Tokitsukaze Kingdom has held his 100th press conference about the global pandemic after making his 1000000th tweets with his smartphone. With a big smile on his face, Mr. Thumb said that nobody knows math more than he doe...

题目描述   Roundgod is obsessive about linear algebra. Let , everyday she will generate a binary vector randomly in . Now she wonders the probability of generating linearly independent vectors in the next days modulo . Formally, it can be proved that the answer has the form of , where and are coprim...

题目描述   Roundgod has an matrix . One day while she's doing her physics homework, she wonders is it possible to define the physical quantity for matrices.As we all know, the pressure satisfies a formula , where is the compressive force and is the base area.  To describe it in maths, Roundgod puts ...

题目描述   Roundgod is obsessive about numbers. Let be the sum of the digits of in decimal notation, is a harmony pair if and only if . Roundgod is given , and she wants to count the number of harmony pairs modulo satisfying . 输入描述   The only line of input contains one integer . 输出描述   Output o...

题目描述   A sequence is called -bag, if and only if it is put in order by some (maybe one) permutations of to . For example, is a valid -bag sequence.  Roundgod is not satisfied with kk-bag, so she put forward part-kk-bag, which is a contiguous subsequence of -bag.  Wcy wants to know if the sequence...