CODEVS1281 Xn数列 (矩阵乘法+快速乘)

真是道坑题，数据范围如此大。

首先构造矩阵 [ f[0] , 1] * [ a,0 ] ^n= [ f[n],1 ]

[ c,1 ]

注意到m, a, c, x0, n, g<=10^18，所以要有类似于二进制分解的方法进行快速乘，防止爆范围。

Program CODEVS1281;
type arr=array[1..2,1..2] of int64;
Program CODEVS1281;
var a,b:arr;
    m,k1,k2,x0,n,mo,p:int64;
function quick(x,y:int64):int64;
var ans:int64;
begin
  ans:=0;
  while y>0 do
    begin
      if y mod 2=1 then ans:=(ans+x) mod m;
      y:=y div 2;
      x:=x*2 mod m;
    end;
    exit(ans);
end;
operator *(a,b:arr) c:arr;
var i,j,k:longint;
    sum:int64;
begin
  fillchar(c,sizeof(c),0);
  for i:=1 to 2 do
    for j:=1 to 2 do
      begin
        sum:=0;
        for k:=1 to 2 do
          sum:=(sum+quick(a[i,k],b[k,j]))mod m;
        c[i,j]:=sum;
      end;
  exit(c);
end;
begin
  readln(m,k1,k2,x0,n,mo);
  a[1,1]:=1; a[1,2]:=0; a[2,1]:=0; a[2,2]:=1;
  b[1,1]:=k1; b[1,2]:=0; b[2,1]:=k2; b[2,2]:=1;
  while n>0 do
    begin
      if n mod 2=1 then a:=a*b;
      n:=n div 2;
      b:=b*b;
    end;
  writeln((quick(x0,a[1,1])+a[2,1]) mod m mod mo);

end.

CODEVS1281 Xn数列 (矩阵乘法+快速乘)

相关推荐