QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 5370. 循环序列

统计

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

有一天小 C 遇到了一个棘手的序列问题,与一般的序列不同,这个序列有无限长!现在有一个下标从 $1$ 开始的无限长的序列 $x_1, x_2, \cdots$。对该序列进行一次操作,会使得操作后的序列 $=x_i + x_{i+1}$。同时小 C 观察到这个序列一开始有一个非常优美的性质:每隔 $n$ 个数开始循环,即 $\forall i, x_i = x_{(i-1) \bmod n + 1}$。

现在小 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 500$,$1 \leq m_i \leq n_i \leq 10^5$,$\sum n_i \leq 10^6$,$1 \leq k_i \leq 10^9$,$1 \leq pos_i \leq n$,$p_i$ 为质数且 $p_i \leq 10^7$,$n_i \mid (p_i - 1)$。