题目描述
F[1][1]=1
F[i,j]=a*F[i][j-1]+b (j!=1)
F[i,1]=c*F[i-1][m]+d (i!=1)
求F[n,m]%1000000007的值
NOI2013
单纯的前50分，可以作为矩阵乘法的模板题，根据二维递推式构造矩阵，快速幂加速递推即可。
对于后30分，可以使用高精度除法，支持除以二的操作即可。
以上随便搞一搞就可以过了（手动@starria）
AC做法#1
黑科技：十进制快速幂！
感觉很容易被卡常，但是仍然有神犇A掉了，想必一定是用了常数极小的矩阵快速幂吧233
AC做法#2
可以推导一下通项公式，之后费马小定理+快速幂秒过对不对！
但是！
费马小定理处理n和m的正确性当且仅当n,m在通项公式中作为指数出现，换句话说，当矩阵的递推元素构成等差数列时，n和m作为系数出现，需要特判。
AC做法#3
矩阵乘法+费马小定理+快速幂加速递推
如果有的小朋友（我）不会求通项公式怎么办？
矩阵乘法就十分友善了233
不过费马小定理的适用性也需要考虑，当a或c等于1的时候，n,m作为系数不能套用费马小定理，同样需要特判。
以上。
PS.我的代码好差啊qaz神犇代码长度连我一半都不到qwq
PPS.话说矩阵你们是怎么用两个数存下来的啊qwq……
代码：
#include<cstdio>
#include<cstring>
#define MOD 1000000007
using namespace std;
struct matrix{
long long t[4][4];
void set(long long a,long long b,long long c,long long d,long long e,long long f,long long g,long long h,long long i){
t[0][0]=a;
t[0][1]=b;
t[0][2]=c;
t[1][0]=d;
t[1][1]=e;
t[1][2]=f;
t[2][0]=g;
t[2][1]=h;
t[2][2]=i;
}
friend matrix operator * (matrix a,matrix b){
matrix res;
res.set(0,0,0,0,0,0,0,0,0);
for(long long i=0;i<3;i++)
for(long long j=0;j<3;j++)
for(long long k=0;k<3;k++){
res.t[i][j]+=(a.t[i][k]*b.t[k][j])%MOD;
res.t[i][j]%=MOD;
}
return res;
}
};
long long n_,m_,a,b,c,d;
char n[1100000],m[1100000];
matrix pow(matrix x,long long n){
matrix tmp=x,res;
res.set(1,0,0,0,1,0,0,0,1);
while(n){
if(n&1){
res=res*tmp;
}
tmp=tmp*tmp;
n>>=1;
}
return res;
}
long long mod(char *x,long long mo){
long long res=0,l=strlen(x);
for(int i=0;i<l;i++){
res*=10;
res%=mo;
res+=(x[i]-'0');
res%=mo;
}
return res;
}
int main(){
scanf("%s%s%lld%lld%lld%lld",&n,&m,&a,&b,&c,&d);
n_=mod(n,a==1?MOD:MOD-1),m_=mod(m,c==1?MOD:MOD-1);
matrix st,t_1,t_2;
st.set(1,b,d,0,0,0,0,0,0);
t_1.set(a,0,0,1,1,0,0,0,1);
t_2.set(c,0,0,0,1,0,1,0,1);
matrix row=pow(t_1,m_-1);
matrix line=pow(row*t_2,n_-1);
st=st*line*row;
printf("%lld\n",st.t[0][0]);
}