[关闭]
@zzzc18 2017-11-09T03:49:02.000000Z 字数 900 阅读 365

矩阵快速幂

模板库


地址

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. typedef long long LL;
  6. LL n;
  7. const LL MOD = 1e9+7;
  8. struct Matrix{
  9. LL mat[5][5];
  10. Matrix(){
  11. memset(mat,0,sizeof(mat));
  12. }
  13. }BASE,A;
  14. Matrix operator * (const Matrix &X,const Matrix &Y){
  15. Matrix re;
  16. for(int i=1;i<=3;i++){
  17. for(int j=1;j<=3;j++){
  18. for(int k=1;k<=3;k++){
  19. re.mat[i][j]+=X.mat[i][k]*Y.mat[k][j]%MOD;
  20. re.mat[i][j]%=MOD;
  21. }
  22. }
  23. }
  24. return re;
  25. }
  26. void DEBUG(Matrix P){
  27. for(int i=1;i<=3;i++){
  28. for(int j=1;j<=3;j++){
  29. printf("%d ",P.mat[i][j]);
  30. }
  31. puts("");
  32. }
  33. }
  34. Matrix qpow(const Matrix &x,LL k){
  35. Matrix mul=x;
  36. Matrix re;
  37. re.mat[1][1]=re.mat[2][2]=re.mat[3][3]=1;
  38. for(LL i=1;i<=k;i<<=1){
  39. if(i&k)
  40. re=mul*re;
  41. mul=mul*mul;
  42. }
  43. return re;
  44. }
  45. int main(){
  46. BASE.mat[1][1]=1;
  47. BASE.mat[1][3]=1;
  48. BASE.mat[2][1]=1;
  49. BASE.mat[3][2]=1;
  50. A.mat[1][1]=A.mat[2][1]=A.mat[3][1]=1;
  51. int kase;
  52. scanf("%d",&kase);
  53. while(kase--){
  54. scanf("%lld",&n);
  55. if(n<=3)
  56. puts("1");
  57. else
  58. printf("%lld\n",(qpow(BASE,n-3)*A).mat[1][1]);
  59. }
  60. return 0;
  61. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注