题目链接：https://vijos.org/p/1725
http://www.lydsy.com/JudgeOnline/problem.php?id=2875
这题是前几年的noi的题，时间比较久远了所以就不是那么的难了
这是一个非常裸的矩阵乘法，一般矩阵乘法就是矩阵+快速幂
只是这道题在矩阵乘法的时候单纯的乘法会溢出，所以还要用到快速乘法
网上也有说用long double黑科技的，虽然我不是很懂那个东东
构造矩阵
单位矩阵a,c
0,1
答案矩阵 Xi-1
1
我的这个矩阵构造可能和一般的不同，主要是我受斐波拉契的毒害太深了QAQ
这题我一开始只是用的int，只过了一半，longlong后过了17组，最后三组加上快速乘优化才成功通过
然后如果是在vijos提交要注意一点就是在vijos上输出longlong型要用I64d来输出
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<queue>
#define ll long long
using namespace std; ll n,m,a,c,g,x0;
ll ans[][],b[][]; void read(ll & xx){
xx=;ll ff=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')ff=-;ch=getchar();}
while(ch>=''&&ch<=''){xx=xx*+ch-'';ch=getchar();}
xx*=ff;
} ll sum(ll x,ll y){
ll cnt=;
while(y){
if(y&){
cnt=(cnt+x)%m;
}y>>=;x=(x+x)%m;
}return cnt;
} void add(){
ll z[][];memset(z,,sizeof(z));
for(int i=;i<=;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
z[i][j]=(z[i][j]%m+sum(b[k][j],b[i][k])%m)%m;
}
}
}
for(int i=;i<=;i++)
for(int j=;j<=;j++)
b[i][j]=z[i][j]%m;
} void mul(ll y){
while(y){
if(y&){
ll z[][];z[][]=z[][]=;
for(int i=;i<=;i++){
for(int j=;j<=;j++){
for(int k=;k<=;k++){
z[i][j]=(z[i][j]%m+sum(ans[k][j],b[i][k])%m)%m;
}
}
}
ans[][]=z[][]%m;
}
y>>=;
add();
}
} int main(){
read(m),read(a),read(c),read(x0),read(n),read(g);
ans[][]=x0%m;ans[][]=;
b[][]=a%m;b[][]=c%m;b[][]=;
mul(n);
//printf("%lld",ans[1][1]%g);
cout<<ans[][]%g;
}
【总结】
活用快速幂的模板，毕竟这东西真的很神奇