等比数列取模求和公式（数字，矩阵皆可）

假设是2*2的矩阵吧，数字类比即可

代码：

struct Matrix
{long long ma[2][2];
};
Matrix res;
Matrix mult(Matrix A,Matrix B)
{Matrix C;memset(C.ma,0,sizeof(C.ma));for(int i=0; i<2; i++)for(int j=0; j<2; j++)for(int k=0; k<2; k++)C.ma[i][j]=(C.ma[i][j]+A.ma[i][k]*B.ma[k][j])%mod;return C;
}
Matrix pow_mod(Matrix A,long long n)
{Matrix B;B.ma[0][0]=B.ma[1][1]=1;B.ma[0][1]=B.ma[1][0]=0;while(n){if(n&1) B=mult(B,A);A=mult(A,A);n>>=1;}return B;
}
Matrix add(Matrix a,Matrix b){for(int i=0;i<2;i++){for(int j=0;j<2;j++){a.ma[i][j]=(a.ma[i][j]+b.ma[i][j])%mod;}}return a;
}
Matrix cal(Matrix A,long long k) ///用二分法求矩阵和,递归实现 计算 a^1+a^2.....+a^p
{if(k==1)return A;else if(k&1)return add(cal(A,k-1),pow_mod(A,k));elsereturn mult(cal(A,k>>1),add(pow_mod(A,k>>1),res));
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！