首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【LightOJ】1006 - Hex-a-bonacci(矩阵快速幂)

【LightOJ】1006 - Hex-a-bonacci(矩阵快速幂)

作者头像
FishWang
发布2025-08-27 11:42:13
发布2025-08-27 11:42:13
8500
代码可运行
举报
运行总次数: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

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

代码如下:(矩阵)

代码语言:javascript
代码运行次数:0
运行
复制
#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的值不大,用递推就行了。

代码如下:

代码语言:javascript
代码运行次数:0
运行
复制
#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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Input
  • Output
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档