POJ3070原题
http://poj.org/problem?id=3070
如图,Fibonacci矩阵解法:
import java.util.Scanner;
public class Main
{
Scanner scan=new Scanner(System.in);
long n;
int w=10000;
long[][] a=new long[2][2];
public static void main(String[] args)
{
new Main().run();
}
long[][] multi(long[][] b,long[][] a)
{
long[][] c=new long[2][2];
for(int i=0;i<b.length;i++)
{
for(int j=0;j<a[i].length;j++)
{
for(int k=0;k<a.length;k++)
{
c[i][j]=(c[i][j]+b[i][k]*a[k][j])%w;
}
}
}
return c;
}
void evaluate()//初始化矩阵
{
a[0][0]=a[0][1]=a[1][0]=1;
a[1][1]=0;
}
//矩阵快速幂
long fastpow(long[][] a,long n)
{
long[][] b=new long[2][2];
b[0][0]=b[1][1]=1;
b[0][1]=b[1][0]=0;
while(n>0)
{
if(n%2==1)
b=multi(b,a);
a=multi(a,a);
n>>=1;//右移一位表示除2
}
return b[0][1];
}
void run()
{
while(true)
{
n=scan.nextLong();
if(n==-1)
break;
else{
evaluate();
long c=fastpow(a,n);
System.out.println(c);
}
}
}
}
- 大小: 2.3 KB
分享到:
相关推荐
2遍dp poj_3613解题报告 poj_3613解题报告
北大pku poj 3070 Fibonacci解题报告源代码 - acm解题报告
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ3982-The Fibonacci sequence 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj3233的代码,利用了面向对象的编程,是复习C++知识的好例子
北大POJ1159-Palindrome 解题报告+AC代码
如题所示,亲测可用。求高精度幂,不会的同学可以参考下,会做的同学可以给挑挑毛病!大家以代码会友!
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码