本文共 1750 字，大约阅读时间需要 5 分钟。
矩阵快速幂计算 #includeusing namespace std;#define ll long longstruct mt{ ll a[3][3];};mt t(mt a, mt b, ll mod){ mt res; int i, j, k; for(i=0; i<3; i++){ for(j=0; j<3; j++){ res.a[i][j] = 0; for(k=0; k<3; k++){ res.a[i][j] += a.a[i][k] * b.a[k][j] % mod; res.a[i][j] %= mod; } } } return res;}mt power(mt a, ll b, ll mod){ mt res; int i, j; for(i=0; i<3; i++){ for(j=0; j<3; j++){ res.a[i][j] = 0; } } res.a[0][0] = res.a[1][1] = res.a[2][2] = 1; while(b){ if(b & 1) res = t(res, a, mod); b >>= 1; a = t(a, a, mod); } return res;}ll feb(ll n, ll mod){ mt temp; int i, j; for(i=0; i<3; i++){ for(j=0; j<3; j++){ temp.a[i][j] = 0; } } temp.a[0][1] = temp.a[1][1] = temp.a[1][0] = 1; mt res = power(temp, n-1, mod); return (res.a[0][0] + res.a[0][1]) % mod;}ll feb2(ll n, ll mod){ mt temp; int i, j; for(i=0; i<3; i++){ for(j=0; j<3; j++){ temp.a[i][j] = 0; } } temp.a[0][1] = temp.a[1][1] = temp.a[1][0] = temp.a[1][2] = temp.a[2][2] = 1; mt res = power(temp, n-1, mod); return (res.a[0][0] + 2*res.a[0][1] + res.a[0][2]) % mod;}ll power(ll a, ll b, ll mod){ ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; b >>= 1; a = (a * a) % mod; } return res;}int main(){ int m = 1e9 + 7; ll n, x, y, a, b; cin >> n >> x >> y >> a >> b; if(n == 1){ cout << "结果为1" << endl; }
优化说明：
转载地址：http://uoewz.baihongyu.com/