2014
02-24

# Tower

Alan loves to construct the towers of building bricks. His towers consist of many cuboids with square base. All cuboids have the same height h = 1. Alan puts the consecutive cuboids one over another:

Recently in math class, the concept of volume was introduced to Alan. Consequently, he wants to compute the volume of his tower now. The lengths of cuboids bases (from top to bottom) are constructed by Alan in the following way:

1. Length a1 of the first square is one.

2. Next, Alan fixes the length a2 of the second square.

3. Next, Alan calculates the length an (n > 2) by 2*a2*(an-1)-(an-2). Do not ask why he chose such

a formula; let us just say that he is a really peculiar young fellow. For example, if Alan fixes a2 = 2, then a3 = 8 -a1 = 7; see Figure 1. If Alan fixes a2 = 1, then an = 1 holds for all n belong to N; see Figure 2.

Now Alan wonders if he can calculate the volume of tower of N consecutive building bricks. Help Alan and write the program that computes this volume. Since it can be quite large, it is enough to compute the answer modulo given natural number m.

The input contains several test cases. The first line contains the number t (t <= 10^5) denoting the number of test cases. Then t test cases follow. Each of them is given in a separate line containing three integers a2,N,m (1 <= a2,m <= 10^9, 2 <= N <= 10^9) separated by a single space, where a2 denotes the fixed length of second square in step 2, while N denotes the number of bricks constructed by Alan.

The input contains several test cases. The first line contains the number t (t <= 10^5) denoting the number of test cases. Then t test cases follow. Each of them is given in a separate line containing three integers a2,N,m (1 <= a2,m <= 10^9, 2 <= N <= 10^9) separated by a single space, where a2 denotes the fixed length of second square in step 2, while N denotes the number of bricks constructed by Alan.

3
2 3 100
1 4 1000
3 3 1000000000

54
4
299
Hint

反复应用递推关系得到：

然后Sn-1利用相同的方式展开，把4tAn-2An-3约去，得到：

这样就比较容易得出Sn的通项：

当初这个题目之所以没想到这种方法，就是因为一看到递推关系，就想着用一般解方程的方法去求解通项，思维被局限了，其实用简单的方式就可以推出来的。以后对于一个问题，应该从多个方面去想，不能想当然啊。想起最近看到的一段话，以此自勉：
正则表达式非常强大，但是它并不能为每一个问题提供正确的解决方案。你应该学习足够多的知识，以辨别什么时候它们是合适的，什么时候它们会解决你的问题，什么时候它们产生的问题比要解决的问题还要多。
一些人，遇到一个问题时就想：“我知道，我将使用正则表达式。”现在他有两个问题了。——Jamie Zawinski

/*
又学了一招了，矩阵中有负数的时候，取模取了之后
if(r.num[i][j] < 0)	r.num[i][j] += mod;
就是因为这里一直错，于是开始乱七不遭地改，郁闷是后来xwc提醒说要考虑
还有就是很奇怪，hdu oj 对于_int64 的要求很不高的，今天试了好多，感觉没有什么不可以的
记得zoj是要用_int64  % I64d 的，有些oj long long int  %lld

*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct Mat
{
_int64 num[4][4];
Mat()
{
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
num[i][j] = 0;
}
};
Mat mul(Mat a, Mat b, _int64 mod)
{
Mat r;
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
r.num[i][j] = 0;
for(int i = 0; i < 4; i++)
for(int k = 0; k < 4; k++)
{

if(a.num[i][k] == 0)
continue;

for(int j = 0; j < 4; j++)
{

if(b.num[k][j] == 0)
continue;

r.num[i][j] =(r.num[i][j] + a.num[i][k] * b.num[k][j]) % mod;
if(r.num[i][j] < 0)
r.num[i][j] += mod;
}

}
return r;
}
Mat mal(Mat a, Mat b, _int64 n, _int64 mod)
{
while(n)
{
if(n & 1)
{
b = mul(a , b, mod);
n--;
}
else
{
a = mul(a, a, mod);
n >>= 1;
}
}
return b;
}
int main()
{
int t;
//cin >> t;
scanf("%d", &t);
while(t--)
{
_int64 a2, n, mod;
//cin >> a2 >> n >> mod;
scanf("%I64d %I64d %I64d", &a2, &n, &mod);
_int64 sum2 = (a2 * a2 + 1) % mod;
_int64 a3 = (2 * a2 * a2 - 1) % mod;
_int64 a4 = (2 * a2 * a3 - a2) % mod;
if(n == 1)
{
cout << "1" << endl;
continue;
}
if(n <= 4)
{
if(n == 3)
sum2 += a3 * a3;
if(n == 4)
sum2 += a3 * a3 + a4 * a4;
cout << sum2 % mod << endl;
continue;
}
Mat init, unit;
for(int i = 0; i < 4; i++)
for(int j = 0; j < 4; j++)
{
init.num[i][j] = 0;
unit.num[i][j] = 0;
}
init.num[0][0] = (4 * a2 *  a2) % mod;	// 这里的取模我一开始是加了的，后来改的时候又去，郁闷
init.num[0][1] = (2 - 8 * a2 * a2) % mod;
init.num[0][2] = (4 * a2 *  a2) % mod;
init.num[0][3] = -1;
init.num[1][0] = 1;
init.num[2][1] = 1;
init.num[3][2] = 1;
unit.num[0][0] = (sum2 + a3 * a3 + a4 * a4) % mod;
unit.num[1][0] = (sum2 + a3 * a3) % mod;
unit.num[2][0] = sum2 % mod;
unit.num[3][0] = 1;
Mat ans;
ans = mal(init, unit, n - 4, mod);
printf("%I64d/n", ans.num[0][0]);
//cout << ans.num[0][0] % mod << endl;
}
}