NIRVANA

Problem

isn

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

给出一个长度为$n$的序列$A\;(A_1,A_2\cdots A_n)$。如果序列$A$不是非降的，你必须从中删去一个数，重复这一操作，直到$A$非降为止。求有多少种不同的操作方案，答案模$10^9+7$。

Input

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

Output

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

Problem

Hard Nim

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$\mathrm{Claris}$和$\mathrm{NanoApe}$在玩石子游戏，他们有$n$堆石子，规则如下：

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

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

Input

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

Output

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

Problem

【CTSC2011】幸福路径

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

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

Input

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

Output

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

Problem

【NOI2013】矩阵游戏

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

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

• $F[1][1]=1$
• $F[i,j]=a\cdot F[i][j-1]+b\;\;(j>1)$
• $F[i,1]=c\cdot F[i-1][m]+d\;\;(i>1)$

递推式中$a,b,c,d$都是给定的常数。
现在婷婷想知道$F[n][m]$的值是多少，请你帮助她。
由于最终结果可能很大，你只需要输出$F[n][m]$除以$10^9+7$的余数。

Input

一行有六个整数$n,m,a,b,c,d$。

Output

包含一个整数，表示$F[n][m]$除以$10^9+7$的余数。

Problem

Problem

Problem

fraction

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

给出$4$个正整数$a,b,c,d$，求一个最简分数$\frac{p}{q}$满足$\frac{a}{b}<\frac{p}{q}<\frac{c}{d}$。
若有多组解，输出$q$最小的一组，若仍有多组解，输出$p$最小的一组。

Input

本题有多组数据，有若干行，每行$4$个数$a,b,c,d$。以文件的末尾作为结束。

Output

对于输入的每组数据输出一个最简分数$\frac{p}{q}$。

Problem

Earthquake

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给定$A,B,C$，求满足方程$Ax+By\le C$的非负整数解的个数。

Input

输入一行三个整数$A,B,C$，含义如上所述。

Output

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

Problem

DZY Loves Math IV

$\mathrm{Time\;Limit:\;15\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给定$n,m$，求$\sum_{i=1}^{n}\sum_{j=1}^{m}\varphi(ij)$模$10^9+7$的值。

Input

仅一行，两个整数$n,m$。

Output

仅一行答案。

Problem

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

时间限制：$\mathrm{2000\;ms}$
内存限制：$\mathrm{256\;MiB}$

题目描述

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

输入格式

输入第一行包含三个正整数$T,m,k$，$T$表示询问组数，$m,k$的含义见题目描述。
接下来$T$行，每行包含一个正整数$n$，表示询问进行$n$次攻击后扣减$\mathrm{Boss}$的生命值点数的期望。

输出格式

输出共$T$行，对于每个询问输出一行一个非负整数，表示该询问的答案对$998244353$取模的结果。
可以证明，所求期望一定是一个有理数，设其为$\frac{p}{q}$（$\gcd(p,q)=1$），那么你输出的数$x$要满足$p\equiv qx\bmod{998244353}$。