矩阵快速幂模板(pascal)

洛谷P3390

题目背景

矩阵快速幂

题目描述

给定n*n的矩阵A,求A^k

输入输出格式

输入格式:

第一行,n,k

第2至n+1行,每行n个数,第i+1行第j个数表示矩阵第i行第j列的元素

输出格式:

输出A^k

共n行,每行n个数,第i行第j个数表示矩阵第i行第j列的元素,每个元素模10^9+7

输入输出样例

输入样例#1:
2 1
1 1
1 1
输出样例#1:
1 1
1 1

说明

n<=100, k<=10^12, |矩阵元素|<=1000

算法:矩阵快速幂

矩阵快速幂模板:

 program rrr(input,output);
const
cs=;
var
a,c,ans:array[..,..]of int64;
n,i,j,k:longint;
m:int64;
begin
assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);
readln(n,m);
for i:= to n do for j:= to n do read(a[i,j]);
fillchar(ans,sizeof(ans),);
for i:= to n do ans[i,i]:=;
while m> do
begin
if m mod = then
begin
//c:=ans*a;
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]+ans[i,k]*a[k,j]) mod cs; end;
//ans:=c;
for i:= to n do for j:= to n do ans[i,j]:=c[i,j];
end;
//c:=a*a;
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]*a[k,j]) mod cs; end;
//a:=c;
for i:= to n do for j:= to n do a[i,j]:=c[i,j];
m:=m>>;
end;
for i:= to n do begin for j:= to n do write(ans[i,j],' ');writeln; end;
close(input);close(output);
end.
上一篇:Powershell下设置环境变量


下一篇:powershell 设置环境变量 -- go 单元测试 exit status 3221225781