链接：https://vjudge.net/problem/OpenJ_POJ-C16H
思路：借着这个题把矩阵快速幂学了，其实原理跟快速幂一样只是把数换成了矩阵而已，首先我们推出公式如下：
image.png
引用自(https://www.cnblogs.com/niwatori1217/p/5689633.html)
由于是周期重复，考虑把一个周期的变化能写成矩阵，那么我们算出这一个周期内的矩阵的对应值，然后m/n个周期内快速幂一下，最后剩余的m%n个直接硬算过去即可得到最终答案。
代码：
#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;
}
