C - Recursive sequence （矩阵ksm）

原题链接：Problem - 5950

Problem Description

Farmer John likes to play mathematics games with his N cows. Recently, they are attracted by recursive sequences. In each turn, the cows would stand in a line, while John writes two positive numbers a and b on a blackboard. And then, the cows would say their identity number one by one. The first cow says the first number a and the second says the second number b. After that, the i-th cow says the sum of twice the (i-2)-th number, the (i-1)-th number, and i4. Now, you need to write a program to calculate the number of the N-th cow in order to check if John’s cows can make it right.

Input

The first line of input contains an integer t, the number of test cases. t test cases follow.
Each case contains only one line with three numbers N, a and b where N,a,b < 231 as described above.

Output

For each test case, output the number of the N-th cow. This number might be very large, so you need to output it modulo 2147493647.

Sample Input

2 3 1 2 4 1 10

Sample Output

85 369

题意：给三个数n a b，规定一个数组，f[i]=2*f[i-2]+f[i-1]+i^4

a是数组的第一个数，b是数组的第二个数

求第n个数是多少（mod2^32）

思路：根据f[i]=2*f[i-2]+f[i-1]+i^4

把i^4展开就是i^4 + 4*i^3+ 6*i^2+ 4*i+ 1

那么我们就需要i^4 i^3 i^2 i 1

构造Fn={fn-2,fn-1,n^4,n^3,n^2,n,1}

那么Fn+1={fn-1,fn,(n+1)^4,(n+1)^3,(n+1)^2,(n+1),1}

那么A矩阵就是：

0 2 0 0 0 0 0

1 1 0 0 0 0 0

0 1 1 0 0 0 0

0 0 4 1 0 0 0

0 0 6 3 1 0 0

0 0 4 3 2 1 0

0 0 1 1 1 1 1

f3数组就是{a,b,81,27,9,3,1}

然后就算出来： f3*A^（n-3）

最后答案就是：2*f3[0][0]+f3[0][1]+f3[0][2];

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=2147493647;
ll n,aa,bb;
void mul(ll c[7][7],ll a[7][7],ll b[7][7]){
	ll temp[7][7]={0};
	for(int i=0;i<7;i++){
		for(int j=0;j<7;j++){
			for(int k=0;k<7;k++){
				temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%mod;
			}
		}
	}
	memcpy(c,temp,sizeof temp);
}
void sove(){
	scanf("%lld%lld%lld",&n,&aa,&bb);
	if(n==1){
		printf("%lld\n",aa);
		return ;
	}
	if(n==2){
		printf("%lld\n",bb);
		return ;
	}
	ll a[7][7]={
	{0,2,0,0,0,0,0},
	{1,1,0,0,0,0,0},
	{0,1,1,0,0,0,0},
	{0,0,4,1,0,0,0},
	{0,0,6,3,1,0,0},
	{0,0,4,3,2,1,0},
	{0,0,1,1,1,1,1},
	};
	ll f3[7][7];
	memset(f3,0,sizeof f3);
	f3[0][0]=aa;
	f3[0][1]=bb;
	f3[0][2]=81;
	f3[0][3]=27;
	f3[0][4]=9;
	f3[0][5]=3;
	f3[0][6]=1;
	ll k=n-3;
	while(k){
		if(k&1)mul(f3,f3,a);
		mul(a,a,a);
		k>>=1;
	}
	ll ans=(2*f3[0][0]+f3[0][1]+f3[0][2])%mod;
	printf("%lld\n",ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		sove();
	}
	return 0;
}