Number Sequence(HDU 1005 构造矩阵 )
2024-10-12 16:35:03
Number Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 147964 Accepted Submission(s): 35964
Problem Description
A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
Sample Input
1 1 3
1 2 1
0
0 0 0
0 0 0
Sample Output
2
5
因为数据量比较大,可以打表找到循环规律,但这种类型的题发现都可以构造矩阵求解
f[n] = a b * f[n-1]
f[n-1] 1 0 f[n-2]
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int a,b,n;
int m[];
struct Matrix
{
int mat[][];
}p;
Matrix mul(Matrix a,Matrix b)
{
Matrix c;
for(int i=;i<;i++)
{
for(int j=;j<;j++)
{
c.mat[i][j]=;
for(int k=;k<;k++)
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%;
}
}
return c;
}
Matrix mod_pow(Matrix x,int n)
{
Matrix res;
memset(res.mat,,sizeof(res.mat));
for(int i=;i<;i++)
res.mat[i][i]=;
while(n)
{
if(n&)
res=mul(res,x);
x=mul(x,x);
n>>=;
}
return res;
}
int main()
{
freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&a,&b,&n)!=EOF)
{
if(a==&&b==&&n==)
break;
if(n<)
{
printf("1\n");
continue;
}
p.mat[][]=a;
p.mat[][]=;
p.mat[][]=b;
p.mat[][]=;
Matrix ans= mod_pow(p,n-);
printf("%d\n",(ans.mat[][]+ans.mat[][])%);
}
}
最新文章
- [转]How to add new table in NopCommerce
- myeclipse的快捷键和myeclipse快捷键设置
- phpstorm 自定义函数配置
- 抽象(abstract)升级版变接口(interface) 继承(extends)升级版叫实现(implements) 升级版啊升级版 接口可以多继承
- 使用Mybatis Generator自动生成Mybatis相关代码
- 在Fragment中使用BaiduMap SDK
- opals 开发记录
- JAVA多线程编程(详细例子)
- 实现各种 CSS3 文本动画效果
- Angular4 - Can&#39;t bind to &#39;ngModel&#39; since it isn&#39;t a known property of &#39;input&#39;.
- 关于chrome浏览器的帐号密码和背景色的填充问题
- Windows下createfile函数用GENERIC_READ访问模式打不开磁盘
- 2018年东北农业大学春季校赛 I-wyh的物品(二分查找)
- CSP 地铁修建 Kruskal (最小生成树+并查集)
- git 出现冲突时的解决办法
- 七:python 对象类型详解三:列表
- 第三百五十二节,Python分布式爬虫打造搜索引擎Scrapy精讲—chrome谷歌浏览器无界面运行、scrapy-splash、splinter
- Spring MVC学习回顾
- (1)RGB-D点云生成
- css中的线及vertical-align