QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+1]

# 5370. 循环序列

Statistics

小C是一个算法竞赛爱好者,他最擅长处理的就是序列问题。

有一天小 C 遇到了一个棘手的序列问题,与一般的序列不同,这个序列有无限长!现在有一个下标从 1 开始的无限长的序列 x1,x2,。对该序列进行一次操作,会使得操作后的序列 =xi+xi+1。同时小 C 观察到这个序列一开始有一个非常优美的性质:每隔 n 个数开始循环,即 i,xi=x(i1)mod

现在小 C 需要解决 q 个问题,每个问题开始时,序列会重置为 0。接下来,小 C 会将这个序列中所有 x_t 都赋为 1,其中 t=m_i + cn_i, c=0,1,2,\cdots 然后小 C 想知道,对这个序列操作 k_i 次后,x_{pos_i} 的值是多少?当然,多次操作后与 x_{pos_i} 的值可能过大,你只需要输出 x_{pos_i} 在模p_i 意义下的取值即可。

输入格式

第一行,包含一个数 q

接下来一行,每行五个数 n_i, m_i, k_i, pos_i, p_i

输出格式

输出 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): n_i \leq 2
  • Subtask 2(20 pts): n_i \leq 20
  • Subtask 3(20 pts): n_i 互不相同,k_i \le 10^6\forall i, j, p_i = p_j
  • Subtask 4(50 pts): 无特殊限制。

对于所有数据,0 \leq q \leq 5001 \leq m_i \leq n_i \leq 10^5\sum n_i \leq 10^61 \leq k_i \leq 10^91 \leq pos_i \leq np_i 为质数且 p_i \leq 10^7n_i \mid (p_i - 1)