这道题其实算是把快速幂的思想用在多项式之中
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
然后就是打码的问题了
1 var ans,a,b,c,f:array[0..30,0..30] of longint; 2 d:array[0..30] of longint; 3 i,j,n,m,p:longint; 4 5 procedure mul; 6 var i,j,k:longint; 7 begin 8 for i:=1 to n do 9 for j:=1 to n do 10 begin 11 c[i,j]:=0; 12 for k:=1 to n do 13 c[i,j]:=(c[i,j]+a[i,k]*b[k,j] mod p) mod p; 14 end; 15 end; 16 17 procedure add; 18 var i,j:longint; 19 begin 20 for i:=1 to n do 21 for j:=1 to n do 22 ans[i,j]:=(ans[i,j]+c[i,j]) mod p; 23 end; 24 25 procedure quick(x:longint); 26 var i,j:longint; 27 begin 28 j:=0; 29 while x<>0 do 30 begin 31 inc(j); 32 d[j]:=x mod 2; 33 x:=x shr 1; 34 end; 35 fillchar(c,sizeof(c),0); 36 for i:=1 to n do 37 c[i,i]:=1; 38 for i:=j downto 1 do 39 begin 40 a:=c; 41 b:=c; 42 mul; 43 if d[i]=1 then 44 begin 45 a:=c; 46 b:=f; 47 mul; 48 end; 49 end; 50 end; 51 52 procedure work(x:longint); 53 begin 54 if x=1 then ans:=f 55 else begin 56 work(x shr 1); 57 quick(x shr 1); 58 a:=c; 59 b:=ans; 60 mul; 61 add; 62 if x mod 2=1 then 63 begin 64 quick(x); 65 add; 66 end; 67 end; 68 end; 69 70 begin 71 readln(n,m,p); 72 for i:=1 to n do 73 for j:=1 to n do 74 read(f[i,j]); 75 work(m); 76 for i:=1 to n do 77 begin 78 for j:=1 to n do 79 begin 80 write(ans[i,j]); 81 if j<>n then write(' '); 82 end; 83 writeln; 84 end; 85 end.