OpenJudge(C16H)(Magical Balls)

链接：https://vjudge.net/problem/OpenJ_POJ-C16H
思路：借着这个题把矩阵快速幂学了，其实原理跟快速幂一样只是把数换成了矩阵而已，首先我们推出公式如下：

image.png

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
const int maxn = 2;

long long t,n,m,x,y;
long long A[20010],B[20010];

struct Martix{
    long long a[maxn][maxn];

    Martix(){
        for(int i=0;i<maxn;i++){
            for(int j=0;j<maxn;j++){
                if(i==j)
                a[i][j] = 1;
            else a[i][j] = 0;
            }
        }
    }

    void init(){
        for(int i=0;i<maxn;i++){
            for(int j=0;j<maxn;j++){
                if(i==j)
                a[i][j] = 1;
            else a[i][j] = 0;
            }
        }
    }

    Martix operator*(const Martix & r){
        Martix res;
        for(int i=0;i<maxn;i++){
            for(int j=0;j<maxn;j++){
                res.a[i][j] = 0;
                for(int k=0;k<maxn;k++){
                    res.a[i][j] = (res.a[i][j] + a[i][k]*r.a[k][j])%mod;
                }
            }
        }
        return res;
    }

    void print(int n,int m){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                printf("%lld ",a[i][j]);
            }
            printf("\n");
        }
    }
};

Martix quick_mod(Martix q,long long w){
    Martix res;
    while(w){
    if(w%2)res = res * q;
        q = q*q;
        w>>=1;
    }
    return res;
}


int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld%lld%lld",&n,&m,&x,&y);
        x = (x%mod+mod)%mod;//注意取模加模再取模
        y = (y%mod+mod)%mod;
        long long pt = n/m;
        long long left = n%m;
        for(int i=1;i<=m;i++){
            long long u,d,l,r;
            scanf("%lld%lld%lld%lld",&u,&d,&l,&r);
            A[i] = 1+u+d+l+r;
            B[i] = u-d+r-l;
        }
        Martix base,r;
        //先算一个周期的，然后快速幂，再补剩下的
        for(int i=1;i<=m;i++){
             r.a[0][0] = A[i];
             r.a[0][1] = 0;
             r.a[1][0] = B[i];
             r.a[1][1] = A[i];
           base = base*r;
        }
        base =  quick_mod(base,pt);
        for(int i=1;i<=left;i++){
             r.a[0][0] = A[i];
             r.a[0][1] = 0;
             r.a[1][0] = B[i];
             r.a[1][1] = A[i];
           base = base*r;
        }
        printf("%lld\n",(base.a[1][0]+base.a[1][1]*(x+y))%mod);
    }
    return 0;
}