矩阵的应用

点击打开链接

点击打开链接

题意】计算的小数点前三位数，不足三位补0,正整数n的最大值为20亿。

【前提】：满足

的值在【0，1】范围

首先将

展开之后可以发现

的形式，同样的，有

因此，

是个整数，

其中

这正是解题的关键！

由于

所以的整数部分等于

根据以上的推导

只要高效的求出an就可以解决这个问题了

由于

为观察仔细，进一步展开得：

得出

的递推关系

因此，可以用矩阵表示这个递推关系，使用矩阵快速幂，在O（logn）的时间里求出和,由于此题只要取前3位，因此对1000取模就可以了。

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const LL siz=2; // max size of the matrix, #define MODD(a,b) (((a%b)+b)%b) LL A,B,N,M,ret; struct mut{ LL mat[siz][siz]; mut(){ memset(mat,0,sizeof(mat)); } void init(LL a,LL b,LL c,LL d){ mat[0][0]=a; mat[0][1]=b; mat[1][0]=c; mat[1][1]=d; } mut operator *(const mut &c){ mut res; for(int i=0; i<siz; ++i){ for(int k=0; k<siz; ++k){ for(int j=0; j<siz; ++j){ res.mat[i][j]=MODD(res.mat[i][j]+mat[i][k]*c.mat[k][j],M); } } } return res; } } AC; mut poww(LL n){ mut ans; ans.init(1,0,0,1); while(n){ if(n&1) ans=ans*AC; n>>=1; AC=AC*AC; } return ans; } int main() { int t; scanf("%d",&t); while(t--){ scanf("%lld",&N); M=1000; AC.init(3,5,1,3); mut ans=poww(N); printf("%03lld\n",MODD(2*ans.mat[0][0]-1,M)); } return 0; }