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的余数。
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
题解：
不看数据范围的话这就是到水题……
前10个点很好过，普通的二进制快速幂就可以
后面10个点如果还用原来的方法，需要涉及高精度除以单精度，复杂度是O(len)的
所以一种新的快速幂诞生了！-----十进制快速幂！
（转）
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
假设咱们需要求 m^n，咱们有一种方法是 二进制快速幂，这个的复杂度是O(logn)的。但是咱们还可以做的更好实际上....咱们把 n拆成10进制表达式，比如 :
234=2*10^2+3*10+4，
139476=1*10^5+3*10^4+9*10^3+4*10^2+7*10^1+6
咱们设拆成的形式是
n=a0+a1*10^1+a2*10^2...+ai*10^i+...+ad*10^d，d为n的最高位，其实就是d=【logn】(log以10为底数）
然后这个表示出来了咱们有：
m^n=m^(a0+a1*10^1+a2*10^2+...+ai*10^i...+ad*10^d)(ak∈【0,9】，k∈【1，d】）
看出一点来了吧...
咱们可以化成 m^n=m^a9*(m^a1)^10*(m^a2)^100....
继续化简，咱们有 m^n=(((m^ad)^10*ad-1)^10*m^ad-2).....
这个实际上就很好做了，由于 0<=ai<=9，只需要预处理下m^0~m^9即可很快计算出m^ai，然后这个就是O(logn)的，(log以10为底)，只不过需要加个10的常数，不过这个的效率在n达到10^100就可以体现了=w=。
即算法流程就是初始化ans=1,从n的最高位开始，每一次提取一位w，用ans乘以m^w然后再做10次的幂，重复到n的所有位都取完了即可。即这个算法的复杂度只与n的位数有关，预处理10个数复杂度也不是很高。
然后取最高位只需要一开始分解每个位存在一个数组里面即可，这里假设是a[]，然后预处理的m^0~9在mm[]里，下面就是伪代码：
function quickmod(n:int64):int64;
begin
len=0;tmp=n
while tmp!=0 do
len=len+1
a[len]=tmp mod 10;
tmp=tmp div 10;
ans=1
for i=len downto 1 do
ans=ans*mm[a[i]]
ans=ans^10
return ans
end
再举个例子吧...
比如 2^154，咱们就有 2^154=((2^1)^10*2^5)^10*2^4 咱们拆开来自然可以检验出这个是不是正确的了。
再比如 2^1512526，咱们就有
2^1512526=((((((2^1)^10*2^5)^10*2^1)^10*2^2)^10*2^5)^10*2^2)^10*2^6
为什么要用十进制快速幂？显然可以发现它的表示实际上比二进制更自然吧...每次只需要取最高位就可以了而不需要考虑什么二进制的原理，显然是十分方便的。而且复杂度比二进制的复杂度更小，还是非常不错了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
我觉得其实十进制快速幂的思想和霍纳法则（或者称之为秦九韶算法）差不多……
代码1：50分 二进制快速幂
const p=;
type matrix=array[..,..] of longint;
var a,b,c:matrix;
i,n,m,a1,a2,b1,b2:longint;
procedure mul(var x,y,z:matrix);
var t:matrix;
i,j,k:longint;
begin
fillchar(t,sizeof(t),);
for i:= to do
for j:= to do
for k:= to do
t[i,j]:=(t[i,j]+x[i,k]*y[k,j]) mod p;
z:=t;
end;
procedure ksm(cs:longint);
begin
while cs> do
begin
if cs and = then mul(a,b,b);
cs:=cs>>;
mul(a,a,a);
end;
end;
procedure init;
begin
readln(n,m,a1,b1,a2,b2);
end;
procedure main;
begin
a[,]:=;a[,]:=b1;a[,]:=;a[,]:=a1;
for i:= to do b[i,i]:=;
ksm(m-);
c:=b;
b[,]:=;b[,]:=b2;b[,]:=;b[,]:=a2;
mul(c,b,a);
fillchar(b,sizeof(b),);
for i:= to do b[i,i]:=;
ksm(n-);
mul(b,c,b);
writeln((b[,]+b[,]) mod p);
end;
begin
init;
main;
end.
代码2：80分 十进制快速幂（后四个点TLE)
const p=;
type matrix=array[..,..] of longint;
arrtype=array[..] of longint;
var a,b,c:matrix;
mm:array[..] of matrix;
i,a1,a2,b1,b2:longint;
n,m:arrtype;
ch:char;
procedure mul(var x,y,z:matrix);
var t:matrix;
i,j,k:longint;
begin
fillchar(t,sizeof(t),);
for i:= to do
for j:= to do
for k:= to do
t[i,j]:=(t[i,j]+x[i,k]*y[k,j]) mod p;
z:=t;
end;
procedure pow10(s:arrtype);
var i,j:longint;t:matrix;
begin
dec(s[s[]]);i:=s[];while s[i]< do begin inc(s[i],);dec(s[i-],);dec(i);end;
fillchar(mm,sizeof(mm),);
for i:= to do mm[,i,i]:=;
for i:= to do mul(mm[i-],a,mm[i]);
fillchar(b,sizeof(b),);
for i:= to do b[i,i]:=;
for i:= to s[] do
begin
mul(b,mm[s[i]],b);
if i=s[] then break;
t:=b;
for j:= to do mul(b,t,b);
end;
end;
procedure init;
begin
read(ch);n[]:=;
while ch<>' ' do
begin
inc(n[]);n[n[]]:=ord(ch)-ord('');
read(ch);
end;
read(ch);m[]:=;
while ch<>' ' do
begin
inc(m[]);m[m[]]:=ord(ch)-ord('');
read(ch);
end;
readln(a1,b1,a2,b2);
end;
procedure main;
begin
a[,]:=;a[,]:=b1;a[,]:=;a[,]:=a1;
pow10(m);
c:=b;
b[,]:=;b[,]:=b2;b[,]:=;b[,]:=a2;
mul(c,b,a);
pow10(n);
mul(b,c,b);
writeln((b[,]+b[,]) mod p);
end;
begin
init;
main;
end.
代码3：80分 考虑把代码二中 ans^10换成二进制快速幂（依然TLE)
const p=;
type matrix=array[..,..] of int64;
arrtype=array[..] of longint;
var a,b,c:matrix;
mm:array[..] of matrix;
i,a1,a2,b1,b2:longint;
n,m:arrtype;
ch:char;
procedure mul(var x,y,z:matrix);
var t:matrix;
i,j,k:longint;
begin
fillchar(t,sizeof(t),);
for i:= to do
for j:= to do
for k:= to do
t[i,j]:=(t[i,j]+x[i,k]*y[k,j]) mod p;
z:=t;
end;
procedure pow10(s:arrtype);
var i,j,cs:longint;tmp:matrix;
begin
dec(s[s[]]);i:=s[];while s[i]< do begin inc(s[i],);dec(s[i-],);dec(i);end;
fillchar(mm,sizeof(mm),);
for i:= to do mm[,i,i]:=;
for i:= to do mul(mm[i-],a,mm[i]);
fillchar(b,sizeof(b),);
for i:= to do b[i,i]:=;
for i:= to s[] do
begin
mul(b,mm[s[i]],b);
if i=s[] then break;
tmp:=b;
fillchar(b,sizeof(b),);
for j:= to do b[j,j]:=;
cs:=;
while cs> do
begin
if cs and = then mul(tmp,b,b);
cs:=cs>>;
mul(tmp,tmp,tmp);
end;
end;
end;
procedure init;
begin
read(ch);n[]:=;
while ch<>' ' do
begin
inc(n[]);n[n[]]:=ord(ch)-ord('');
read(ch);
end;
read(ch);m[]:=;
while ch<>' ' do
begin
inc(m[]);m[m[]]:=ord(ch)-ord('');
read(ch);
end;
readln(a1,b1,a2,b2);
end;
procedure main;
begin
a[,]:=;a[,]:=b1;a[,]:=;a[,]:=a1;
pow10(m);
c:=b;
b[,]:=;b[,]:=b2;b[,]:=;b[,]:=a2;
mul(c,b,a);
pow10(n);
mul(b,c,b);
writeln((b[,]+b[,]) mod p);
end;
begin
init;
main;
end.
代码4：受兰多夫87的影响，考虑修改矩阵乘法，应为第一列始终是不变的 （为什么还是TLE啊…………）
const p=;
type matrix=array[..,..] of int64;
arrtype=array[..] of longint;
var a,b,c:matrix;
mm:array[..] of matrix;
i,a1,a2,b1,b2:longint;
n,m:arrtype;
ch:char;
procedure mul(var x,y,z:matrix);
var t:matrix;
i,j,k:longint;
begin
fillchar(t,sizeof(t),);
t[,]:=;t[,]:=;
for i:= to do
for k:= to do
t[i,]:=(t[i,]+x[i,k]*y[k,]) mod p;
z:=t;
end;
procedure pow10(s:arrtype);
var i,j,cs:longint;tmp:matrix;
begin
dec(s[s[]]);i:=s[];while s[i]< do begin inc(s[i],);dec(s[i-],);dec(i);end;
fillchar(mm,sizeof(mm),);
for i:= to do mm[,i,i]:=;
for i:= to do mul(mm[i-],a,mm[i]);
fillchar(b,sizeof(b),);
for i:= to do b[i,i]:=;
for i:= to s[] do
begin
mul(b,mm[s[i]],b);
if i=s[] then break;
tmp:=b;
fillchar(b,sizeof(b),);
for j:= to do b[j,j]:=;
cs:=;
while cs> do
begin
if cs and = then mul(tmp,b,b);
cs:=cs>>;
mul(tmp,tmp,tmp);
end;
end;
end;
procedure init;
begin
read(ch);n[]:=;
while ch<>' ' do
begin
inc(n[]);n[n[]]:=ord(ch)-ord('');
read(ch);
end;
read(ch);m[]:=;
while ch<>' ' do
begin
inc(m[]);m[m[]]:=ord(ch)-ord('');
read(ch);
end;
readln(a1,b1,a2,b2);
end;
procedure main;
begin
a[,]:=;a[,]:=b1;a[,]:=;a[,]:=a1;
pow10(m);
c:=b;
b[,]:=;b[,]:=b2;b[,]:=;b[,]:=a2;
mul(c,b,a);
pow10(n);
mul(b,c,b);
writeln((b[,]+b[,]) mod p);
end;
begin
init;
main;
end.
代码5：我认为是我写丑了 膜拜兰多夫87吧
const p=;
type matrix=array[..] of int64;
arrtype=array[..] of longint;
var x,y:matrix;
z:array[..] of matrix;
i,a,b,c,d:longint;
n,m:arrtype;
ch:char;
operator *(a,b:matrix)c:matrix;
begin
c[]:=a[]*b[] mod p;
c[]:=(b[]*a[]+b[]) mod p;
end;
function f(x:matrix;var a:arrtype):matrix;
var i:longint;y:matrix;
begin
dec(a[a[]]);i:=a[];
while a[i]< do begin inc(a[i],);dec(a[i-]);dec(i);end;
z[,]:=;z[,]:=;
for i:= to do z[i]:=z[i-]*x;
x:=z[];
for i:= to a[] do
begin
y:=x*x;
x:=x*y*y;
x:=x*x;
x:=x*z[a[i]];
end;
exit(x);
end;
procedure init;
begin
read(ch);n[]:=;
while ch<>' ' do
begin
inc(n[]);n[n[]]:=ord(ch)-ord('');
read(ch);
end;
read(ch);m[]:=;
while ch<>' ' do
begin
inc(m[]);m[m[]]:=ord(ch)-ord('');
read(ch);
end;
readln(a,b,c,d);
end;
procedure main;
begin
x[]:=a;x[]:=b;
x:=f(x,m);
y[]:=c;y[]:=d;
y:=x*y;
y:=f(y,n);
y:=y*x;
writeln((y[]+y[]) mod p);
end;
begin
assign(input,'matrix.in');assign(output,'matrix.out');
reset(input);rewrite(output);
init;
main;
close(input);close(output);
end.
无限orz！
看来养成一个好的代码风格是必要的