矩阵快速幂

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int M=2;
const int mod=10000;
struct node{
    int m[M][M];
    node operator*(node const &b)const{
        node res;
        memset(res.m,0,sizeof(res.m));
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                for(int k=0;k<M;k++)
                    res.m[i][j]=(res.m[i][j]+this->m[i][k]*b.m[k][j])%mod;
        return res;
    }
};
node quick(node base,int b)
{
    node t;
    t.m[1][1]=t.m[0][0]=1;
    t.m[1][0]=t.m[0][1]=0;
    while(b)
    {
        if(b&1)
            t=t*base;
        b>>=1;
        base=base*base;
    }
    return t;
}
int main()
{
    node s;
    s.m[0][0]=s.m[0][1]=s.m[1][0]=1;
    s.m[1][1]=0;
    int n;
    while(~scanf("%d",&n)&&n!=-1)
    {
        if(n==0)
        {
            printf("0
");
            continue;
        }
        node sum;
        sum=quick(s,n);
        printf("%d
",sum.m[0][1]);
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
int n;
const int mod=9973;
const int M=10;
struct node{
    int m[M][M];
    node operator*(node const &b)const{
        node res;
        memset(res.m,0,sizeof(res.m));
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                for(int k=0;k<n;k++)
                    res.m[i][j]=(res.m[i][j]+this->m[i][k]*b.m[k][j])%mod;
        return res;
    }
};
int quick(node &a,int k)
{
    node t;
    memset(t.m,0,sizeof(t.m));
    for(int i=0;i<n;i++)
        t.m[i][i]=1;
    while(k)
    {
        if(k&1)
            t=t*a;
        k>>=1;
        a=a*a;
    }
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        sum+=t.m[i][i];
        sum%=mod;
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int k;
        scanf("%d%d",&n,&k);
        node a;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&a.m[i][j]);
        printf("%d
",quick(a,k));
    }
    return 0;
}

/*题目要求的是(sqrt(2)+sqrt(3))^2n %1024向下取整的值
(sqrt(2)+sqrt(3))^2n=((sqrt(2)+sqrt(3))^2)n=(5+2*sqrt(6))^n
改式子一定可以表示为f(x)=a[x]+b[x]*sqrt(6);
所以f(x)=f(x-1)*(5+2*sqrt(6));
既f(x)=(5+2*sqrt(6)*(a[x-1]+b[x-1]*sqrt(6)));
|5  12|*|a[n-1]|=|a[n]|
|2  5 |*|b[n-1]|=|b[n]|
因此矩阵快速幂；
然后就是取数的问题了，向下取整 
由(5+2*sqrt(6))^n=a[n]+b[n]*sqrt(6)    (5-2*sqrt(6))^n=a[n]-b[n]*sqrt(6);
所以(5+2*sqrt(6))^n+(5-2*sqrt(6))^n=2*a[n];
因为(5-2*sqrt(6))^n约等于0；
所以(5+2*sqrt(6))^n+0=2*a[n];
所以(5+2*sqrt(6))^n=2*a[n]-1(向下取整）
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=2;
const int mod=1024;
const double P=sqrt((double)6);
struct node{
    int m[M][M];
    node operator*(const node &b)const{
        node res;
        memset(res.m,0,sizeof(res.m));
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                for(int k=0;k<M;k++)
                    res.m[i][j]=(res.m[i][j]+this->m[i][k]*b.m[k][j])%mod;
        return res;
    }
};
int quick(node &a,int b)
{
    if(b==1)
        return 9;
    node t;
    memset(t.m,0,sizeof(t.m));
    for(int i=0;i<M;i++)
        t.m[i][i]=1;
    b--;
    while(b)
    {
        if(b&1)
            t=t*a;
        b>>=1;
        a=a*a;
    }
    int suma=0;
    suma+=(t.m[0][0]*5+t.m[0][1]*2)%mod;
    return(2*suma-1)%mod;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        node a;
        memset(a.m,0,sizeof(a.m));
        a.m[0][0]=5;
        a.m[0][1]=12;
        a.m[1][0]=2;
        a.m[1][1]=5;
        printf("%d
",quick(a,n));
    }
    return 0;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int M=2;
typedef long long ll;
ll mod;
struct node{
    int m[M][M];
    node operator*(node const &b)const{
        node res;
        memset(res.m,0,sizeof(res.m));
        for(int i=0;i<M;i++)
            for(int j=0;j<M;j++)
                for(int k=0;k<M;k++)
                    res.m[i][j]=(res.m[i][j]+this->m[i][k]*b.m[k][j])%mod;
        return res;
    }
};
node jksm(node base,int b){
    node t;
    t.m[0][0]=t.m[1][1]=1;
    t.m[0][1]=t.m[1][0]=0;
    while(b){
        if(b&1)
            t=t*base;
        b>>=1;
        base=base*base;
    }
    return t;
}
ll ksm(ll a,ll b,ll modd){
    ll t=1;
    while(b){
        if(b&1){
            t=t*a;
            t%=modd;
        }
        b>>=1;
        a=a*a;
        a%=modd;
    }
    return t;
}
int main(){
    int t;
    scanf("%d",&t);
    for(int k=1;k<=t;k++){
        ll x;
        scanf("%lld%lld",&x,&mod);
        node ans;
        ans.m[0][0]=5;
        ans.m[0][1]=12;
        ans.m[1][0]=2;
        ans.m[1][1]=5;
        x=ksm(2ll,x,(mod-1)*(mod+1))+1;
        ans=jksm(ans,x);
        ll sum=(2*ans.m[0][0]-1)%mod;
        printf("Case #%d: ",k);
        printf("%lld
",sum);
    }
    return 0;
}