BZOJ4589 Hard Nim < FWT >
Problem
Hard Nim
TimeLimit:10Sec
MemoryLimit:128MB
Description
Claris和NanoApe在玩石子游戏,他们有n堆石子,规则如下:
- Claris和NanoApe两个人轮流拿石子,Claris先拿。
- 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。
不同的初始局面,决定了最终的获胜者,有些局面下先拿的Claris会赢,其余的局面Claris会负。
Claris很好奇,如果这n堆石子满足每堆石子的初始数量是不超过m的质数,而且他们都会按照最优策略玩游戏,那么NanoApe能获胜的局面有多少种。
由于答案可能很大,你只需要给出答案对109+7取模的值。
Input
输入文件包含多组数据,以EOF
为结尾。
对于每组数据,输入一行两个正整数n和m。
Output
对于每组数据,输出一行一个整数表示答案。
BZOJ2306【CTSC2011】幸福路径 <概率DP>
Problem
【CTSC2011】幸福路径
TimeLimit:10Sec
MemoryLimit:256MB
Description
有向图G有n个顶点1,2,⋯,n,点i的权值为wi。现在有一只蚂蚁,从给定的起点v0出发,沿着图G的边爬行。
开始时,它的体力为1。每爬过一条边,它的体力都会下降为原来的p倍,其中p是一个给定的小于1的正常数。而蚂蚁爬到某个顶点时的幸福度,是它当时的体力与该点权值的乘积。
我们把蚂蚁在爬行路径上幸福度的总和记为H。很显然,对于不同的爬行路径,H的值也可能不同。小Z对H值的最大可能值很感兴趣,你能帮助他计算吗?
注意,蚂蚁爬行的路径长度可能是无穷的。
Input
每一行中两个数之间用一个空格隔开。
输入文件第一行包含两个正整数n,m,分别表示G中顶点的个数和边的条数。
第二行包含n个非负实数,依次表示n个顶点权值w1,w2,⋯,wn。
第三行包含一个正整数v0,表示给定的起点。
第四行包含一个实数p,表示给定的小于1的正常数。
接下来m行,每行两个正整数x,y,表示<x,y>是G的一条有向边。
可能有自环,但不会有重边。
Output
仅包含一个实数,即H值的最大可能值,四舍五入到小数点后一位。
BZOJ3240【NOI2013】矩阵游戏 <欧拉定理>
Problem
【NOI2013】矩阵游戏
TimeLimit:10Sec
MemoryLimit:256MB
Description
婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。
她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:
- F[1][1]=1
- F[i,j]=a⋅F[i][j−1]+b(j>1)
- F[i,1]=c⋅F[i−1][m]+d(i>1)
递推式中a,b,c,d都是给定的常数。
现在婷婷想知道F[n][m]的值是多少,请你帮助她。
由于最终结果可能很大,你只需要输出F[n][m]除以109+7的余数。
Input
一行有六个整数n,m,a,b,c,d。
Output
包含一个整数,表示F[n][m]除以109+7的余数。
BZOJ5418【NOI2018】屠龙勇士 < 扩展CRT >
BZOJ5415【NOI2018】归程 < 最短路+Kruskal重构树+DFS序+线段树 >
BZOJ2187 fraction <类欧几里得>
BZOJ2987 Earthquake <类欧几里得>
BZOJ3512 DZY Loves Math IV <莫比乌斯反演+杜教筛>
LOJ2325「清华集训2017」小Y和恐怖的奴隶主 <概率DP+矩阵快速幂>
Problem
「清华集训2017」小Y和恐怖的奴隶主
时间限制:2000ms
内存限制:256MiB
题目描述
"A fight? Count me in!"
要打架了,算我一个。
"Everyone, get in here!"
所有人,都过来!
小Y是一个喜欢玩游戏的OIer。一天,她正在玩一款游戏,要打一个Boss。
虽然这个Boss有10100点生命值,但它只带了一个随从――一个只有m点生命值的“恐怖的奴隶主”。
这个“恐怖的奴隶主”有一个特殊的技能:每当它被扣减生命值但没有死亡(死亡即生命值≤0),且Boss的随从数量小于上限k,便会召唤一个新的具有m点生命值的“恐怖的奴隶主”。
现在小Y可以进行n次攻击,每次攻击时,会从Boss以及Boss的所有随从中的等概率随机选择一个,并扣减1点生命值,她想知道进行n次攻击后扣减Boss的生命值点数的期望。为了避免精度误差,你的答案需要对998244353取模。
输入格式
输入第一行包含三个正整数T,m,k,T表示询问组数,m,k的含义见题目描述。
接下来T行,每行包含一个正整数n,表示询问进行n次攻击后扣减Boss的生命值点数的期望。
输出格式
输出共T行,对于每个询问输出一行一个非负整数,表示该询问的答案对998244353取模的结果。
可以证明,所求期望一定是一个有理数,设其为qp(gcd(p,q)=1),那么你输出的数x要满足p≡qxmod998244353。