BZOJ3240 [Noi2013]矩阵游戏

时间:2022-12-04 17:32:38

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

Description

婷婷是个喜欢矩阵的小朋友,有一天她想用电脑生成一个巨大的n行m列的矩阵(你不用担心她如何存储)。她生成的这个矩阵满足一个神奇的性质:若用F[i][j]来表示矩阵中第i行第j列的元素,则F[i][j]满足下面的递推式:

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)
递推式中a,b,c,d都是给定的常数。

现在婷婷想知道F[n][m]的值是多少,请你帮助她。由于最终结果可能很大,你只需要输出F[n][m]除以1,000,000,007的余数。

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

Input

一行有六个整数n,m,a,b,c,d。意义如题所述

Output

包含一个整数,表示F[n][m]除以1,000,000,007的余数

Sample Input

3 4 1 3 2 6

Sample Output

85

HINT

样例中的矩阵为:

1 4 7 10

26 29 32 35

76 79 82 85

1<=N,M<=10^1000 000,a<=a,b,c,d<=10^9

正解:费马小定理+快速幂+递推公式

解题报告:

  大多数题解写的都是矩乘+快速幂的,感觉不用那么麻烦,只需要一点点高一课堂上讲过的推出递推式子就可以了。

  推导过程其实挺简单的,就是根据那个式子,先推导出f[i,m]和f[i,1]的关系,然后得到f[i+1,1],再根据新的式子得到f[n+1,1]和f[1,1]的关系,反推得到f[n,m]即可。

  具体推导的话直接复制别人的了,很详细:(参考博客链接:http://www.cnblogs.com/iiyiyi/p/5617598.html)

BZOJ3240 [Noi2013]矩阵游戏

 //It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int inf = (<<);
const int MAXN = ;
const int mod = ;
const int MOD = ;
int n,m,len;
int k1[],k2[];
int mi[]={,,,,,,,,};
char ch[MAXN];
LL a,b,c,d,A,B,ans,ans2,C,D;
//A=c*a^(m-1)
//B=( ( b*c*(a^(m-1)-1) ) / (a-1) )+d inline int getint()
{
int w=,q=; char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
}
inline LL fastpow(LL x,LL y){
if(x== || y==) return ;
LL base=x,r=;
while(y>) {
if(y&) r*=base,r%=mod;
base*=base; base%=mod; y>>=;
}
return r;
}
inline LL ni(LL x){ return fastpow(x,mod-); }
inline LL fastpow_m(){
LL res=; LL mm=;//对指数取模
for(int i=;i<=m;i++) res+=mm*k2[i]%(mod-),mm*=MOD,mm%=(mod-),res%=(mod-);
return fastpow(a,res);
/*
LL r=1,base=a;
while(m) {
if(k2[1]&1) r*=base,r%=mod;
base*=base; base%=mod;
for(int i=m;i>=1;i--) {
if(k2[i]&1) k2[i-1]+=MOD;
k2[i]>>=1;
}
while(k2[m]==0 && m>0) m--;
}
return r;*/
} inline LL fastpow_n(LL di){
LL res=; LL mm=;//对指数取模
for(int i=;i<=n;i++) res+=mm*k1[i]%(mod-),mm*=MOD,mm%=(mod-),res%=(mod-);
return fastpow(di,res);
/*
LL r=1,base=di;
while(n) {
if(k1[1]&1) r*=base,r%=mod;
base*=base; base%=mod;
for(int i=n;i>=1;i--) {
if(k1[i]&1) k1[i-1]+=MOD;
k1[i]>>=1;
}
while(k1[n]==0 && n>0) n--;
}
return r;*/
} inline void getAB(){
A=fastpow_m(); A*=ni(a); A%=mod; //A=a^(m-1)
B=A; B--; B*=b; B%=mod; B*=c; B%=mod;
B*=ni(a-); B%=mod; B+=d; B%=mod; A*=c; A%=mod;
} inline void over(){
ans-=d; ans+=mod; ans%=mod; ans*=ni(c); ans%=mod;
printf("%lld",ans);
} inline void work(){
scanf("%s",ch); len=strlen(ch); n=; int now=;
int gi=;
for(int i=len-;i>=;i--) {
now=now+(ch[i]-'')*mi[gi];//!!!
gi++;
if(now>=MOD || gi>=) {
gi=;//!!!
k1[n]+=now%MOD;
k1[++n]=now/MOD;
now=;//!!!
}
}
k1[n]+=now; while(k1[n]==) n--; scanf("%s",ch); len=strlen(ch); m=; now=;
gi=;
for(int i=len-;i>=;i--) {
now=now+(ch[i]-'')*mi[gi]; gi++;
if(now>=MOD || gi>=) {
gi=;
k2[m]+=now%MOD;
k2[++m]=now/MOD;
now=;
}
}
k2[m]+=now; while(k2[m]==) m--;
a=getint(); b=getint(); c=getint(); d=getint();
if(a!=) {
getAB();
if(A!=) {
ans=fastpow_n(A); ans%=mod;
ans2=ans-; ans2+=mod; ans2%=mod; ans2*=B; ans2%=mod;
ans2*=ni(A-); ans2%=mod; ans+=ans2; ans%=mod;
}
else{//特判A==1
LL res=,mm=; for(int i=;i<=n;i++) res+=mm*k1[i]%mod,mm*=MOD,mm%=mod,res%=mod;
ans=res*B; ans++; ans%=mod;
}
over();
}
else {
D=c*b; D%=mod; LL res=,mm=;
for(int i=;i<=m;i++) res+=mm*k2[i]%mod,mm*=MOD,mm%=mod,res%=mod;
res--; res+=mod; res%=mod; D*=res; D%=mod; D+=d; D%=mod;
if(c==) {
res=; mm=; for(int i=;i<=n;i++) res+=mm*k1[i]%mod,mm*=MOD,mm%=mod,res%=mod;
D*=res; D%=mod; ans=D+;
over();
}
else{
C=fastpow_n(c);
ans=C; C-=; C*=ni(c-); C%=mod;
ans+=D*C; ans%=mod;
over();
}
}
} int main()
{
work();
return ;
}