[NOI2013]矩阵游戏
此题解法大约两种，矩阵乘法和推式子
都说一下
矩阵乘法
构造一下矩阵
把(egin{bmatrix}a & 0 \b & 1end{bmatrix})称为(A),(egin{bmatrix}c & 0 \d & 1end{bmatrix})称作(B)
答案就是(egin{bmatrix}1 & 1 \0 & 0end{bmatrix} imes A^{n(m-1)} imes B^{n-1})这个矩阵的左上角元素
搭配十进制快速幂可获得80~100不等的分数
然后一些dalao发现元素会有循环，若a=1，循环节为1e9+7，否则为1e9+6
循环节在每行，每列都会循环，所以n,m取模即可
妥妥的AC
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#include<cstring>
#define il inline
#define rg register
#define vd void
#define sta static
#define int long long
#define mod 1000000007
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
struct yyb{
int a,b,c,d;
yyb(int _a=1,int _b=0,int _c=0,int _d=1){a=_a%mod,b=_b%mod,c=_c%mod,d=_d%mod;}
};
yyb operator *(const yyb&a,const yyb&b){
return (yyb){
a.a*b.a+a.b*b.c, a.a*b.b+a.b*b.d,
a.c*b.a+a.d*b.c, a.c*b.b+a.d*b.d
};
}
char N[1000100],M[1000100];
int a,b,c,d,lenn,lenm,n,m;
yyb operator ^(yyb a,int b){
yyb ret;
while(b){
if(b&1)ret=ret*a;
a=a*a;b>>=1;
}
return ret;
}
main(){
scanf("%s%s%lld%lld%lld%lld",N+1,M+1,&a,&b,&c,&d);
lenn=strlen(N+1),lenm=strlen(M+1);
if(a!=1){
for(rg int i=1;N[i];++i)n=(n*10+N[i]-'0')%(mod-1);
for(rg int i=1;M[i];++i)m=(m*10+M[i]-'0')%(mod-1);
if(!n)n=mod-1;if(!m)m=mod-1;
}else{
for(rg int i=1;N[i];++i)n=(n*10+N[i]-'0')%mod;
for(rg int i=1;M[i];++i)m=(m*10+M[i]-'0')%mod;
if(!n)n=mod;if(!m)m=mod;
}
yyb S=(yyb){1,1,0,0},A=(yyb){a,0,b,1},B=(yyb){c,0,d,1};
A=(((A^(m-1))*B)^(n-1))*(A^(m-1));
printf("%lld
",(S*A).a);
return 0;
}
暴力推式子
考虑从(F[i][1])到(F[i+1][1])的变化。
这个和随稽数生成器那题有点像（那道题保证互质就能用这个方法AC了）
(a e 1:)
(F[i][m]=a^{m-1}F[i][1]+b(a^0+a^1+cdotcdotcdot+a^{m-2})=a^{m-1}F[i][1]+b imesfrac{a^{m-1}}{a-1})
(F[i+1][1]=a^{m-1} imes c imes F[i][1]+b imes c imesfrac{a^{m-1}}{a-1}+d)
令(p=a^{m-1} imes c,q=b imes c imesfrac{a^{m-1}}{a-1}+d)
可以发现(F[i+1][1]=p imes F[i][1]+q)
(a = 1:)
(F[i][m]=F[i][1]+b(m-1))
(F[i+1][1]=c imes F[i][1]+b(m-1) imes c+d)
这时的(p=c,q=b(m-1) imes c+d)
再按上述方法推一次可算出(F[n+1][1])
减d除c即可得到答案
n和m好像也可以按矩阵的方法取模。。然后蜜汁85
贴上吧：
// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
#define int long long
#define mod 1000000007
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
il int pow(int x,int y){
int ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}
return ret;
}
char nn[1000001],mm[1000001];
int n,m,a,b,c,d;
main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%s%s",nn+1,mm+1);
for(rg int i=1;nn[i];++i)n=(n*10+nn[i]-'0')%(mod-1);
for(rg int i=1;mm[i];++i)m=(m*10+mm[i]-'0')%(mod-1);
a=gi(),b=gi(),c=gi(),d=gi();
int A,B,ans;
if(a==1)A=c,B=(b*c%mod*(m-1)%mod+d)%mod;
else{
int p=pow(a,m-1);
A=p*c%mod,B=(b*c%mod*(p-1)%mod*pow(a-1,mod-2)%mod+d)%mod;
}
if(A==1)ans=(1+B*n)%mod;
else{
int p=pow(A,n);
ans=(p+B*(p-1)%mod*pow(A-1,mod-2)%mod)%mod;
}
printf("%lld
",(ans-d+mod)%mod*pow(c,mod-2)%mod);
return 0;
}