首页 > 代码库 > 西南民大oj（矩阵快速幂）
西南民大oj（矩阵快速幂）
我的名字不可能那么难记
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 16 测试通过 : 9
View Code
总提交 : 16 测试通过 : 9
描述
Nirvava:Hi,Misaki,听说ZC要离开了..
Misaki:好走不送,祝一帆风顺…
Nirvana: 但他留了好多doge给我们…
Misaki:……
Nirvana:而且他们还有名字，名字如下。
据说ZC离去的原因之一就是因为第N个doge老是问他能不能记住它的名字。
Misaki:记别人名字什么的，好烦哒，ZC肯定记不住。
Nirvana:ZC当然记得，毕竟是他的宠物嘛。难倒他的是，doge的第二个问题：我的名字有多长。ZC难住了，因为他数着数着就doge精神污染了。
Misaki:这个问题，，真的好难..不过，，他们应该能解决。
PS:这个题面是不是有点熟♂悉,懒得想题面了，就把以前的题面拿出来了。
输入
多组输入
每组一个N（0<N<=10^9)
输出
第N个doge的名字有多长，由于可能太长，你只需要输出长度%1000000007(1e9+7)的结果即可。
样例输入
1
2
3
4
500
样例输出
1
3
7
17
875025602
提示
name[1]="X"
name[2]="XXY"
name[3]="XXYXXYX"
name[4]="XXYXXYXXXYXXYXXXY"
……
以此类推。
分析：设a[i]为总长度，b[i]为X的个数，c[i]为Y的个数，则有a[i]=3*b[i-1]+c[i-1],b[i]=2*b[i-1]+c[i-1],c[i]=b[i-1].
则可构造矩阵
|0,0,0|
|a[i-1] ,b[i-1],c[i-1]|*|3,2,1|=|a[i],b[i],c[i]|
|1,1,0|
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 1000010using namespace std;struct matrix{ LL m[3][3];};LL n;matrix mult(matrix a,matrix b){ matrix c; memset(c.m,0,sizeof(c.m)); for(int i=0;i<3;i++) for(int k=0;k<3;k++) { if(a.m[i][k]==0)continue; for(int j=0;j<3;j++) { if(b.m[k][j]==0)continue; c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod; c.m[i][j]%=mod; } } return c;}matrix quickmod(matrix a,LL n){ matrix temp; memset(temp.m,0,sizeof(temp.m)); for(int i=0;i<3;i++)temp.m[i][i]=1; while(n) { if(n&1)temp=mult(temp,a); a=mult(a,a); n>>=1; } return temp;}int main(){ while(scanf("%lld",&n)!=EOF) { if(n==1){puts("1");continue;} matrix ans; memset(ans.m,0,sizeof(ans.m)); ans.m[0][0]=0;ans.m[0][1]=0;ans.m[0][2]=0; ans.m[1][0]=3;ans.m[1][1]=2;ans.m[1][2]=1; ans.m[2][0]=1;ans.m[2][1]=1;ans.m[2][2]=0; ans=quickmod(ans,n-1); printf("%lld\n",ans.m[1][0]); }}
西南民大oj（矩阵快速幂）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。