bzoj2326

时间:2021-04-26 19:22:31

首先不难得出递推式f[i]=(f[i-1]*10^k+i) mod m;
f[i]表示接到第i个数时的余数,k表示i的位数
不难想到先按位数穷举位数,然后对于确定的位数,构造矩阵解决
易得出:
f[i]    10^k  1   1      f[i-1] 
 i   =   0    1   1   *    i-1
 1       0    0   1         1
矩阵乘法优化的特点就是有一维特别的大,且这一阶段的值只和上一阶段有关

 var a,b,w,c:array[..,..] of int64;
f,p:array[..] of int64;
d:array[..] of longint;
e:array[..] of int64;
j,i,l,m:longint;
x,n:int64; procedure mul1;
var i,j,k:longint;
begin
for i:= to do
for j:= to do
begin
c[i,j]:=;
for k:= to do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j] mod m) mod m;
end;
end; procedure mul2;
var i,k:longint;
begin
for i:= to do
begin
f[i]:=;
for k:= to do
f[i]:=(f[i]+c[i,k]*p[k] mod m) mod m;
end;
end; procedure quick(x:int64);
var i,j:longint;
begin
j:=;
while x> do
begin
inc(j);
d[j]:=x mod ;
x:=x div ;
end;
fillchar(c,sizeof(c),);
for i:= to do
c[i,i]:=;
for i:=j downto do
begin
a:=c;
b:=c;
mul1;
if d[i]= then
begin
a:=c;
b:=w;
mul1;
end;
end;
end; begin
readln(n,m);
e[]:=;
l:=;
for i:= to do
begin
e[i]:=e[i-]*;
if e[i]>n then
begin
l:=i;
break;
end;
end;
e[]:=e[] mod m* mod m;
x:=;
w[,]:=e[] mod m; w[,]:=; w[,]:=;
w[,]:=; w[,]:=; w[,]:=;
w[,]:=; w[,]:=; w[,]:=;
f[]:=; f[]:=; f[]:=;
if l<> then x:=
else x:=n-;
p:=f;
quick(x);
mul2;
x:=;
for i:= to l do
begin
p:=f;
if i<>l then x:=x*
else x:=n-e[i-]+; //防止爆int64的
w[,]:=e[i] mod m;
quick(x);
mul2;
end;
writeln(f[]);
end.

相关文章