【矩阵快速幂】hyper Fibonacci 数列

Description
令F(i)表示斐波那契数列的第i项。
S1(i)表示F数列的前i项和。
S2(i)表示S1数列的前i项和。
S3(i)表示S2数列的前i项和。
S4(i)表示S3数列的前i项和。
S5(i)表示S4数列的前i项和。
S6(i)表示S5数列的前i项和。
S7(i)表示S6数列的前i项和。
S8(i)表示S7数列的前i项和。
求S8(N)。答案可能很大,请对1000000007取模。
斐波那契数列的定义可以查看https://baike.baidu.com/item/斐波那契数列

Input
多组数据。
输入的第一行包括一个整数表示数据组数T(1<=T<=1000)。
每组数据的第一行包括一个整数表示题目所说的N(1<=N<=1000000000000000000)。

Output
每组数据在单独的一行中输出S8(N)。


Sample Input
4
1
2
3
4
Sample Output
1
9
46
175
HINT
F数列前四项:1 1 2 3

S1数列前四项:1 2 4 7

S2数列前四项:1 3 7 14

S3数列前四项:1 4 11 25

S4数列前四项:1 5 16 41

S5数列前四项:1 6 22 63

S6数列前四项:1 7 29 92

S7数列前四项:1 8 37 129

S8数列前四项:1 9 46 175 

由题目给的hint其实已经看出来了\(S_n^8=S_{n-1}^{87654321}+F_n\)

其他项也是如此

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p=1000000007;
struct Mat{
	ll a[10][10];
	Mat(){
		memset(a,0,sizeof(a));
	}
};
Mat mul(Mat a,Mat b)
{
	Mat res=Mat();
	for(ll i=0;i<10;i++)
	{
		for(ll j=0;j<10;j++)
		{
			for(ll k=0;k<10;k++)
			{
				if(a.a[i][k]&&b.a[k][j])
				res.a[i][j]+=(a.a[i][k]%p)*(b.a[k][j]%p)%p;	
			}	
		}	
	}	
	return res;
} 
Mat ksm(Mat n,ll k)
{
	Mat ans=Mat();
	for(ll i=0;i<10;i++)
	ans.a[i][i]=1;
	while(k)
	{
		if(k&1) ans=mul(n,ans);
		n=mul(n,n);
		k>>=1;
	}
	return ans;
}
int main()
{
	ll t;
	ll temp1[10][10]={
		{1,1,1,1,1,1,1,1,1,0},
		{0,1,1,1,1,1,1,1,1,0},
		{0,0,1,1,1,1,1,1,1,0},
		{0,0,0,1,1,1,1,1,1,0},
		{0,0,0,0,1,1,1,1,1,0},
		{0,0,0,0,0,1,1,1,1,0},
		{0,0,0,0,0,0,1,1,1,0},
		{0,0,0,0,0,0,0,1,1,0},
		{0,0,0,0,0,0,0,0,1,1},
		{0,0,0,0,0,0,0,0,1,0}
		};
	ll temp2[10][10]={
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0},
		{1,0,0,0,0,0,0,0,0,0}
		};
	scanf("%lld",&t);
	for(ll i=1;i<=t;i++)
	{
		ll n;
		scanf("%lld",&n);
		Mat a=Mat();		
		memcpy(a.a,temp1,sizeof(temp1));
		Mat inim=Mat();		
		memcpy(inim.a,temp2,sizeof(temp2));
		Mat d=Mat();
		d=mul(ksm(a,n-1),inim);
		printf("%lld\n",d.a[0][0]%p);
	}
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注