2915:数列-2

时间限制:2 S   /  内存限制:5120 KB
AC:136   /  Submit:456
问题描述

有一个数列,a[1] = 1,a[2] = 2,当 n >= 3 时:a[n] = 4 * a[n - 1] - 3 * a[n - 2],你的任务是计算这个数列的第 x 项。

输入描述

第一行是一个正整数 T 代表测试案例的数量。(1 <= T <= 1000)

每组案例包含一个正整数 x 。

对于30%的样例,x <= 1e3。

对于60%的样例,x <= 1e6。

对于100%的样例,x <= 1e10。

输出描述

针对每组案例,输出数列的第 x 项,然后换行。

由于答案可能很大,所以你只需要输出它对(2 ^ 31)取模之后的结果。

样例输入复制样例

3

1

2

10

样例输出

1

2

9842

相关

TKK-ICPC Round#9

题单#1(位运算、快速幂)


Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1