最近开始由线段树转移新的内容，线段树学到扫描线这里有点迷迷糊糊的，有时候放一放可能会好一些。
最近突然对各种数学问题很感兴趣。好好钻研了一下矩阵快速幂。发现矩阵真是个计算神器，累乘类的运算原本要O（N）的复杂度一下子给降到Log（N），非常大的进步了。
这个题目算是矩阵快速幂的比较难推的一个题目。题目要求 （sqrt(2)+sqrt(3)）的 2^n并%1024，要求出值来并不难，构造矩阵即可，但是要mod1024就有问题了，小数不能直接mod，但是如果你取整之后再mod，结果绝逼出问题，因为浮点数的精度问题。
所以从斌牛的博客上看到如此推算，推算第一块不难，而且很容易求出Xn 和 Yn，但是问题又出来了，要是求出来后，直接用（int）（Xn+Yn*sqrt（6））%1024，又会出问题，还是浮点数取整问题，我一开始就这么算的，导致结果奇葩。看来在mod的时候有浮点数要格外注意，直接处理的话，不管怎么取整，都会出问题。
所以分割线下面的推算就避开了这个问题，这个确实好难想到，通过变换一下，得到最终的结果必定是2Xn-（0.101...）^n,因为最终mod是用不大于浮点数的最大整数在mod，所以最终结果就是2Xn-1.第二条确实好难想到！
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; struct Mat{ int mat[2][2]; }; Mat E,a; Mat operator *(Mat a,Mat b) { Mat c; memset(c.mat,0,sizeof (Mat)); for(int i=0;i<2;i++) for (int j=0;j<2;j++) for (int k=0;k<2;k++) { if (a.mat[i][k]>0 && b.mat[k][j]>0) c.mat[i][j]+=a.mat[i][k]*b.mat[k][j]; c.mat[i][j]%=1024; } return c; } Mat operator ^(Mat ac,int x) { Mat c; c=E; for (;x;x>>=1) { //cout<<c.mat[0][0]<<" is "<<endl; if (x&1) c=c*ac; ac=ac*ac; } return c; } void init() { memset(E.mat,0,sizeof (Mat)); // memset(a.mat,0,sizeof (Mat)); a.mat[0][0]=5; a.mat[0][1]=12; a.mat[1][0]=2; a.mat[1][1]=5; for (int i=0;i<2;i++) E.mat[i][i]=1; } int main() { init(); int t; scanf("%d",&t); while (t--) { int n; scanf("%d",&n); Mat s=a^(n-1); int q1=s.mat[0][0]*5+s.mat[0][1]*2; int ans=(q1*2-1)%1024; printf("%d ",ans); } return 0; }