POJ 3070 矩阵快速幂

2019-04-13 15:44发布

站内文章 / 模拟电子
16070 0 1777
矩阵幂模； 可以参考：  

HDU 1420 蒙哥马利幂模算法


不同之处，在于，一个是 数字，一个是矩阵；原理都一样；

/* *problem ID: POJ 3070 * Author ID: fuqiang * TIME: 2013-07-17 * Algorithm: 幂模 * Status: (Accept) */ #include #include #include #include #include using namespace std; #define maxn 2 struct matrix //矩阵 { __int64 arr[maxn][maxn]; }origin,res; matrix multiply(matrix a, matrix b) //矩阵乘法 { matrix temp; memset(temp.arr,0,sizeof(temp.arr)); for(int i = 0; i < maxn; i++) { for(int j = 0; j < maxn; j++) { for(int k = 0; k < maxn; k++) { temp.arr[i][j] += a.arr[i][k]*b.arr[k][j]; } } } return temp; } inline void mod_1w(matrix & k) //mod 10000 { for(int i = 0; i < maxn; i++) { for(int j = 0; j < maxn; j++) { k.arr[i][j] %= 10000; } } } matrix caclo(matrix a,int n,matrix k) //快速幂模 { mod_1w(a); while(n) { if(n&1) { k = multiply(k,a); mod_1w(k); } a = multiply(a,a); mod_1w(a); n >>= 1; } return k; } void InIt() { origin.arr[0][0] = origin.arr[0][1] = origin.arr[1][0] = 1; origin.arr[1][1] = 0; memset(res.arr,0,sizeof(res.arr)); for(int i = 0; i < maxn; i++) //置为单位阵 res.arr[i][i] = 1; } int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==-1) break; InIt(); matrix ans = caclo(origin,n,res); printf("%I64d ",ans.arr[0][1]); } return 0; }

热门文章