Problem

isn

Description

给出一个长度为的序列。如果序列不是非降的，你必须从中删去一个数，重复这一操作，直到非降为止。求有多少种不同的操作方案，答案模。

Input

第一行一个整数。
接下来一行个整数，描述。

Output

一行一个整数，描述答案。

Problem

Hard Nim

Description

和在玩石子游戏，他们有堆石子，规则如下：

1. 和两个人轮流拿石子，先拿。
2. 每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。

不同的初始局面，决定了最终的获胜者，有些局面下先拿的会赢，其余的局面会负。
很好奇，如果这堆石子满足每堆石子的初始数量是不超过的质数，而且他们都会按照最优策略玩游戏，那么能获胜的局面有多少种。
由于答案可能很大，你只需要给出答案对取模的值。

Input

输入文件包含多组数据，以EOF为结尾。
对于每组数据，输入一行两个正整数和。

Output

对于每组数据，输出一行一个整数表示答案。

Problem

【CTSC2011】幸福路径

Description

有向图有个顶点，点的权值为。现在有一只蚂蚁，从给定的起点出发，沿着图的边爬行。
开始时，它的体力为。每爬过一条边，它的体力都会下降为原来的倍，其中是一个给定的小于的正常数。而蚂蚁爬到某个顶点时的幸福度，是它当时的体力与该点权值的乘积。
我们把蚂蚁在爬行路径上幸福度的总和记为。很显然，对于不同的爬行路径，的值也可能不同。对值的最大可能值很感兴趣，你能帮助他计算吗？
注意，蚂蚁爬行的路径长度可能是无穷的。

Input

每一行中两个数之间用一个空格隔开。
输入文件第一行包含两个正整数，分别表示中顶点的个数和边的条数。
第二行包含个非负实数，依次表示个顶点权值。
第三行包含一个正整数，表示给定的起点。
第四行包含一个实数，表示给定的小于的正常数。
接下来行，每行两个正整数，表示是G的一条有向边。
可能有自环，但不会有重边。

Output

仅包含一个实数，即值的最大可能值，四舍五入到小数点后一位。

Problem

【NOI2013】矩阵游戏

Description

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的行列的矩阵(你不用担心她如何存储)。
她生成的这个矩阵满足一个神奇的性质：若用来表示矩阵中第行第列的元素，则满足下面的递推式:

递推式中都是给定的常数。
现在婷婷想知道的值是多少，请你帮助她。
由于最终结果可能很大，你只需要输出除以的余数。

Input

一行有六个整数。

Output

包含一个整数，表示除以的余数。

Problem

Problem

Problem

DZY Loves Math IV

Description

给定，求模的值。

Input

仅一行，两个整数。

Output

仅一行答案。

Problem

fraction

Description

给出个正整数，求一个最简分数满足。
若有多组解，输出最小的一组，若仍有多组解，输出最小的一组。

Input

本题有多组数据，有若干行，每行个数。以文件的末尾作为结束。

Output

对于输入的每组数据输出一个最简分数。

Problem

Earthquake

Description

给定，求满足方程的非负整数解的个数。

Input

输入一行三个整数，含义如上所述。

Output

输出一行一个整数，表示非负整数解的个数。

Problem

「清华集训2017」小Y和恐怖的奴隶主

时间限制：
内存限制：

题目描述

"A fight? Count me in!" 要打架了，算我一个。
"Everyone, get in here!" 所有人，都过来！
是一个喜欢玩游戏的。一天，她正在玩一款游戏，要打一个。
虽然这个有点生命值，但它只带了一个随从――一个只有点生命值的“恐怖的奴隶主”。
这个“恐怖的奴隶主”有一个特殊的技能：每当它被扣减生命值但没有死亡（死亡即），且的随从数量小于上限，便会召唤一个新的具有点生命值的“恐怖的奴隶主”。
现在可以进行次攻击，每次攻击时，会从以及的所有随从中的等概率随机选择一个，并扣减点生命值，她想知道进行次攻击后扣减的生命值点数的期望。为了避免精度误差，你的答案需要对取模。

输入格式

输入第一行包含三个正整数，表示询问组数，的含义见题目描述。
接下来行，每行包含一个正整数，表示询问进行次攻击后扣减的生命值点数的期望。

输出格式

输出共行，对于每个询问输出一行一个非负整数，表示该询问的答案对取模的结果。
可以证明，所求期望一定是一个有理数，设其为（），那么你输出的数要满足。