大家好,欢迎来到IT知识分享网。
时间限制 1000 ms 内存限制 32768 KB 代码长度限制 100 KB 判断程序 Standard (来自 小小)
题目描述
星际战争开展了100年之后,NowCoder终于破译了外星人的密码!他们的密码是一串整数,通过一张表里的信息映射成最终4位密码。表的规则是:n对应的值是矩阵X的n次方的左上角,如果这个数不足4位则用0填充,如果大于4位的则只输出最后4位。 |1 1|^n => |Xn ..| |1 0| |.. ..| 例如n=2时, |1 1|^2 => |1 1| * |1 1| => |2 1| |1 0| |1 0| |1 0| |1 1| 即2对应的数是“0002”。
输入描述:
输入有多组数据。 每组数据两行:第一行包含一个整数n (1≤n≤100);第二行包含n个正整数Xi (1≤Xi≤10000)
输出描述:
对应每一组输入,输出一行相应的密码。
输入例子:
6 18 15 21 13 25 27 5 1 10 100 1000 10000
输出例子:
418109877711037713937811 00010089410135017501
题解:矩阵快速幂裸题,斐波那契矩阵
代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define MOD 10000
using namespace std;
typedef long long int ll;
struct mat
{
ll a[4][4];
}ans,res;
mat Mul(mat x,mat y)
{
mat t;
memset(t.a,0,sizeof(t.a));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
t.a[i][j]+=(x.a[i][k]*y.a[k][j]);
t.a[i][j]%=MOD;
}
}
}
return t;
}
void quickMod(long long int N)
{
ans.a[0][0]=1;
ans.a[0][1]=0;
ans.a[1][0]=0;
ans.a[1][0]=1;
while(N)
{
if(N&1)
{
ans=Mul(ans,res);
}
res=Mul(res,res);
N>>=1;
}
}
int main()
{
ll n;
while(scanf("%lld",&n)!=EOF)
{
int k;
for(int t=0;t<n;t++)
{
scanf("%d",&k);
res.a[0][0]=1;
res.a[0][1]=1;
res.a[1][0]=1;
res.a[1][1]=0;
quickMod(k);
printf("%04lld",ans.a[0][0]);
}
printf("\n");
}
return 0;
}
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/32586.html