#PQJ1086x5370. QOJ 1086_5370
QOJ 1086_5370
标题: 循环序列 - Problem - QOJ.ac
The problem was used in the following contests:
小C是一个算法竞赛爱好者,他最擅长处理的就是序列问题。
有一天小 C 遇到了一个棘手的序列问题,与一般的序列不同,这个序列有无限长!现在有一个下标从 1 开始的无限长的序列 x1,x2,⋯。对该序列进行一次操作,会使得操作后的序列 =xi+xi+1。同时小 C 观察到这个序列一开始有一个非常优美的性质:每隔 n 个数开始循环,即 ∀i,xi=x(i−1)modn+1。
现在小 C 需要解决 q 个问题,每个问题开始时,序列会重置为 0。接下来,小 C 会将这个序列中所有 xt 都赋为 1,其中 t=mi+cni,c=0,1,2,⋯ 然后小 C 想知道,对这个序列操作 ki 次后,xposi 的值是多少?当然,多次操作后与 xposi 的值可能过大,你只需要输出 xposi 在模pi 意义下的取值即可。
输入格式
第一行,包含一个数 q。
接下来一行,每行五个数 ni,mi,ki,posi,pi。
输出格式
输出 q 行,每行一个数,表示每个询问的答案。
样例数据
样例输入
10
4 3 2 3 9900101
5 5 5 1 9900091
6 5 1 4 9900091
40 38 14 6 9900161
46 14 31 9 9900857
49 15 33 12 9901627
390 175 377 238 9900931
335 240 466 328 9907291
2653 1204 3563 891 9911609
3872 3142 4144 1787 9908449
样例输出
1
5
1
0
169911
5456
762581
7846051
5523436
2847830
子任务
- Subtask 1(10 pts): ni≤2
- Subtask 2(20 pts): ni≤20
- Subtask 3(20 pts): ni 互不相同,ki≤106,∀i,j,pi=pj。
- Subtask 4(50 pts): 无特殊限制。
对于所有数据,0≤q≤500,1≤mi≤ni≤105,∑ni≤106,1≤ki≤109,1≤posi≤n,pi 为质数且 pi≤107,ni∣(pi−1)。