#P8791. [2017年江苏]B 君的回忆

    ID: 8885 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>数论动态规划记忆化搜索CF2500模运算矩阵递归多项式

[2017年江苏]B 君的回忆

B君的回忆(erinnerung)

题目描述

给定整数 a,ba,b,定义下标为任意整数的序列 gg:

$$g_0=a,\qquad g_1=b,\qquad g_i=3g_{i-1}-g_{i-2}\quad(i\ge2).$$

负下标通过反向递推唯一确定:

gi=3gi+1−gi+2(i<0).g_i=3g_{i+1}-g_{i+2}\quad(i<0).

再定义

fn,0=n,fn,k=fgn,k−1(k≥1).f_{n,0}=n,\qquad f_{n,k}=f_{g_n,k-1}\quad(k\ge1).

嵌套计算中即使下标为负,也按上述定义求值。求 fn,kf_{n,k} 对 pp 取模的结果。 这里取模仅作用于最终结果,不改变整数序列本身的定义。

输入格式

第一行一个整数 TT,表示数据组数。 接下来 TT 行,每行五个整数 a,b,n,k,pa,b,n,k,p。

输出格式

每组数据输出一行一个整数,位于 [0,p−1][0,p-1],表示答案。

样例

1
0 1 2 2 1000
8

样例解释

g2=3g_2=3,g3=8g_3=8,所以 f2,2=f3,1=f8,0=8f_{2,2}=f_{3,1}=f_{8,0}=8。

数据范围

1≤T≤10001\le T\le1000,0≤a,b<p0\le a,b<p,1≤n,p≤1091\le n,p\le10^9,1≤k≤1001\le k\le100。 其中20%的数据满足 k≤1k\le1,60%的数据满足 k≤2k\le2。

参考附件

原题资料(本页约定为准)