Array Challenge

Problem Description

There’s an array that is generated by following rule.
h 0 =2,h 1 =3,h 2 =6,h n =4h n−1 +17h n−2 −12h n−3 −16 
And let us define two arrays b n anda n   as below.
b n =3h n+1 h n +9h n+1 h n−1 +9h 2 n +27h n h n−1 −18h n+1 −126h n −81h n−1 +192(n>0) 
a n =b n +4 n  
Now, you have to print ⌊√(a n )⌋  , n>1.
Your answer could be very large so print the answer modular 1000000007.

Input

The first line of input contains T (1 <= T <= 1000) , the number of test cases.
Each test case contains one integer n (1 < n <= 10 15   ) in one line.

Output

For each test case print &#8970;√(a_n )&#8971; modular 1000000007.

Sample Input

3
4
7
9

Sample Output

1255
324725
13185773

看起来非常难。

试着用程序列出了一下h和a的前几个数然后就发现h的公式稍微改一下就是a的公式，稍微有个坑，算an的值直接取模的话会有负数的情况，所以先加上mod再取模就可以了。

h n =4h n−1 +17h n−2 −12h n−3 −16 

a n =4a n−1 +17a n−2 −12a n−3 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define mod 1000000007
//http://acm.split.hdu.edu.cn/diy/contest_show.php?cid=32494
using namespace std;
typedef long long ll;

struct matrix{
	int row,col;
	ll A[20][20];
	matrix(int Row=0,int Col=0){
		memset(A,0,sizeof(A));
		row=Row;col=Col;
	}
};

matrix operator *(matrix a,matrix b){
	matrix c(a.row,b.col);
	for(int i=0;i<a.row;i++)
		for(int j=0;j<b.col;j++)
			for(int k=0;k<a.col;k++)
				c.A[i][j]=(c.A[i][j]+a.A[i][k]*b.A[k][j]+mod)%mod;
	return c;
}

matrix matrix_pow(matrix a,ll n){
	matrix ans(a.row,a.col);
	for(int i=0;i<a.row;i++)
			ans.A[i][i]=1;
	while(n){
		if(n%2)
			ans=a*ans;
		a=a*a;
		n/=2;
	}
	return ans;
}

int main()
{
	ll n,T;
	matrix a(3,3);
	a.A[0][0]=4;
	a.A[0][1]=17;
	a.A[0][2]=-12;
	a.A[1][0]=1;
	a.A[1][1]=0;
	a.A[1][2]=0;
	a.A[2][0]=0;
	a.A[2][1]=1;
	a.A[2][2]=0;
	matrix x1(3,3),xn(3,3);
	x1.A[0][0]=1255;
	x1.A[1][0]=197;
	x1.A[2][0]=31;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		xn=matrix_pow(a,n-2)*x1;
		printf("%lld\n",xn.A[2][0]);
	}
	return 0;
 }