这道题其实算是把快速幂的思想用在多项式之中
A+A^2+A^3+…+A^n=(A+A^1…+A^[n/2])+A^[n/2](A+A+A^1…+A^[n/2])+n mod 2*A^n
然后就是打码的问题了
var ans,a,b,c,f:array[..,..] of longint;
d:array[..] of longint;
i,j,n,m,p:longint; procedure mul;
var i,j,k:longint;
begin
for i:= to n do
for j:= to n do
begin
c[i,j]:=;
for k:= to n do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j] mod p) mod p;
end;
end; procedure add;
var i,j:longint;
begin
for i:= to n do
for j:= to n do
ans[i,j]:=(ans[i,j]+c[i,j]) mod p;
end; procedure quick(x:longint);
var i,j:longint;
begin
j:=;
while x<> do
begin
inc(j);
d[j]:=x mod ;
x:=x shr ;
end;
fillchar(c,sizeof(c),);
for i:= to n do
c[i,i]:=;
for i:=j downto do
begin
a:=c;
b:=c;
mul;
if d[i]= then
begin
a:=c;
b:=f;
mul;
end;
end;
end; procedure work(x:longint);
begin
if x= then ans:=f
else begin
work(x shr );
quick(x shr );
a:=c;
b:=ans;
mul;
add;
if x mod = then
begin
quick(x);
add;
end;
end;
end; begin
readln(n,m,p);
for i:= to n do
for j:= to n do
read(f[i,j]);
work(m);
for i:= to n do
begin
for j:= to n do
begin
write(ans[i,j]);
if j<>n then write(' ');
end;
writeln;
end;
end.