矩阵快速幂模

2019-04-13 12:15发布

站内文章 / 模拟电子
12804 0 1581
#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector vec; typedef vector mat; const ll M=1000000007; mat mul(mat &A,mat &B){ mat C(A.size(),vec(B[0].size())); for(int i=0;i0){ if(n&1) B=mul(B,A); A=mul(A,A); n>>=1; } return B; } int main(){ ll x,y,n; while(cin>>x>>y>>n){ mat A(2,vec(2)); A[0][0]=1;A[0][1]=-1; A[1][0]=1;A[1][1]=0; A=pow(A,n-1); // printf("%d ",A[1][0]); int ret=((A[1][0]*y+A[1][1]*x)%M+M)%M; cout<

热门文章