POJ3070 矩阵快速幂模板

题目：http://poj.org/problem?id=3070

矩阵快速幂模板。mod写到乘法的定义部分就行了。

别忘了 I ( ) 和 i n i t ( ) 要传引用！

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,p=10000; struct Matrix{int a[2][2];Matrix operator *(const Matrix &b)const{Matrix c;c.a[0][0]=c.a[1][0]=c.a[0][1]=c.a[1][1]=0;for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)for(int k=0;k<=1;k++)(c.a[i][j]+=a[i][k]*b.a[k][j])%=p; // printf("i=%d j=%d c=%d\n",i,j,b.a[i][j]);return c;} }; Matrix r,u; void I(Matrix &k) {k.a[0][0]=k.a[1][1]=1;k.a[0][1]=k.a[1][0]=0; } void init(Matrix &k) {k.a[0][0]=k.a[0][1]=k.a[1][0]=1;k.a[1][1]=0; } int main() {while(1){scanf("%d",&n);if(n==-1)return 0;if(!n){printf("0\n");continue;}n--;I(r);init(u);while(n){if(n&1)r=r*u;n>>=1;u=u*u;}printf("%d\n",(r.a[1][0]+r.a[1][1])%p);} }

 

转载于:https://www.cnblogs.com/Narh/p/8981926.html

总结

以上是生活随笔为你收集整理的POJ3070 矩阵快速幂模板的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。