hiho 1143 矩阵快速幂求递推式

题目链接：

hihocoder 1143

思路见题目上

快速幂模板：

// m^n % kint quickpow(int m,int n,int k){int b = 1;while (n > 0){if (n & 1)b = (b*m)%k;n = n >> 1 ;m = (m*m)%k;}return b;}

题解：

#include<iostream>#include<cstdio>#include<cstring>#define MOD 19999997using namespace std;struct Matrix{long long m[2][2]; //一定要long long };Matrix mult(Matrix a,Matrix b){Matrix t;for(int i=0;i<2;i++)for(int j=0;j<2;j++)t.m[i][j]=(a.m[i][0]*b.m[0][j])%MOD+(a.m[i][1]*b.m[1][j])%MOD; //long long 不会爆return t;}int m_fastpow(int n){Matrix unit={1,0,0,1};//单位矩阵Matrix x={0,1,1,1};//递推式while(n>0){if(n&1)unit=mult(x,unit);x=mult(x,x);n=n>>1;}return unit.m[1][1]%MOD;}int main(){int n;scanf("%d",&n);printf("%d\n",m_fastpow(n));return 0;}

，发现一种久违的感动。

相关文章：

你感兴趣的文章：

标签云：