【LightOJ】1006 - Hex-a-bonacci（矩阵快速幂）

FishWang

发布于 2025-08-27 11:42:13

13800

代码可运行

运行总次数：0

代码可运行

点击打开题目

1006 - Hex-a-bonacci

	PDF (English)	Statistics	Forum

Time Limit: 0.5 second(s)	Memory Limit: 32 MB

Given a code (not optimized), and necessary inputs, you have to find the output of the code for the inputs. The code is as follows:

int a, b, c, d, e, f; int fn( int n ) { if( n == 0 ) return a; if( n == 1 ) return b; if( n == 2 ) return c; if( n == 3 ) return d; if( n == 4 ) return e; if( n == 5 ) return f; return( fn(n-1) + fn(n-2) + fn(n-3) + fn(n-4) + fn(n-5) + fn(n-6) ); } int main() { int n, caseno = 0, cases; scanf("%d", &cases); while( cases-- ) { scanf("%d %d %d %d %d %d %d", &a, &b, &c, &d, &e, &f, &n); printf("Case %d: %d\n", ++caseno, fn(n) % 10000007); } return 0; }

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains seven integers, a, b, c, d, e, f and n. All integers will be non-negative and 0 ≤ n ≤ 10000 and the each of the others will be fit into a 32-bit integer.

Output

For each case, print the output of the given code. The given code may have integer overflow problem in the compiler, so be careful.

Sample Input	Output for Sample Input
5 0 1 2 3 4 5 20 3 2 1 5 0 1 9 4 12 9 4 5 6 15 9 8 7 6 5 4 3 3 4 3 2 54 5 4	Case 1: 216339 Case 2: 79 Case 3: 16636 Case 4: 6 Case 5: 54

没有计算好时间复杂度，用了矩阵快速幂来做，矩阵的推倒就不细说了。最下面附上简单写法。

代码如下：（矩阵）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define LL long long
#define PI acos(-1.0)
#define MAX 6
LL MOD = 10000007;
struct Matrix
{
	LL m[MAX+5][MAX+5];
	int w,h;
}pr,res,ori;
void init()
{
	pr.w = pr.h = 6;
	CLR(pr.m , 0);
	for (int i = 1 ; i <= pr.h ; i++)
		pr.m[i][1] = 1;
	for (int i = 1 ; i <= 5 ; i++)
		pr.m[i][i+1] = 1;
	
	res.w = res.h = 6;
	CLR(res.m,0);
	for (int i = 1 ; i <= 6 ; i++)
		res.m[i][i] = 1;
}
Matrix Matrix_multiply(Matrix x,Matrix y)
{
	Matrix t;
	t.h = x.h;
	t.w = y.w;
	CLR(t.m,0);
	for (int i = 1 ; i <= x.h ; i++)
	{
		for (int j = 1 ; j <= x.w ; j++)
		{
			if (x.m[i][j] == 0)
				continue;
			for (int k = 1 ; k <= y.w ; k++)
				t.m[i][k] = (t.m[i][k] + x.m[i][j] * y.m[j][k] % MOD) % MOD;
		}
	}
	return t;
}
void Matrix_mod(int n)
{
	while (n)
	{
		if (n & 1)
			res = Matrix_multiply(res , pr);
		pr = Matrix_multiply(pr , pr);
		n >>= 1;
	}
}
int main()
{
	int u;
	int Case = 1;
	int n;
	scanf ("%d",&u);
	while (u--)
	{
		init();
		ori.w = 6;
		ori.h = 1;
		CLR(ori.m , 0);
		for (int i = 6 ; i >= 1 ; i--)
		{
			scanf ("%lld",&ori.m[1][i]);
			ori.m[1][i] %= MOD;
		}
		scanf ("%d",&n);
		printf ("Case %d: ",Case++);
		if (n <= 5)
		{
			printf ("%lld\n",ori.m[1][6-n]);
			continue;
		}
		Matrix_mod(n-5);
		res = Matrix_multiply(ori,res);
		printf ("%lld\n",res.m[1][1]);
	}
	return 0;
}

但是实际上，n的值不大，用递推就行了。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
int a[10010];
int main()
{
	int u,ca=1;
	scanf("%d",&u);
	while(u--)
	{
		for(int i=0;i<6;i++)
		{
			scanf("%d",&a[i]);
			a[i]=a[i]%10000007;
		}
		int n;
		scanf("%d",&n);
		for(int i=6;i<=n;i++)
		{
			a[i]=a[i-1]+a[i-2]+a[i-3]+a[i-4]+a[i-5]+a[i-6];
			a[i]=a[i]%10000007;
		}
		printf("Case %d: %d\n",ca++,a[n]);
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

matrix