1. 首页
  2. Let's OI!
  3. 正文

poj3233Matrix Power Series【矩阵乘法】

  • 内容
  • 评论
  • 相关

题目点击这里

题目大意：给定一个矩阵A，求A+A^2+A^3+...+A^N的值mod m。

N很大，所以暴力显然不靠谱，但是矩阵的等比数列不像实数的等比数列，无法使用一个公式弄出矩阵的等比数列前N项和，但是可以用类似于秦九韶算法的东东：

A+A^2+A^3+…+A^k

=A(1+A(1+A)….(1+A))

=(1+A)^k-1

这样我们可以想办法构造矩阵，弄出这个东东的值。

首先注意到单位矩阵I：IA=A，所以可以把A和I丢到一个大的矩阵进行矩阵乘法。

定义矩阵：
|A|I|
|0|I|

那么它的K+1次方就是：
|A^(K+1)|1+A+A^2+...+A^K|
|0      |I              |

这样用快速幂就搞定了。

PS：注意mod m。

代码：

var
  a,b,c:array[1..60,1..60]of longint;
  n,m,i,j,k,l:longint;
begin
  read(n,k,m);
  for i:=1 to n do
  for j:=1 to n do
  begin
    read(a[i,j]);
    a[i,j]:=a[i,j] mod m;
  end;
  for i:=1 to n do
  begin
    a[i,n+i]:=1;
    a[n+i,n+i]:=1;
  end;
  b:=a;
  //inc(k);
  n:=n*2;
  repeat
    if k mod 2=1 then
    begin
      fillchar(c,sizeof(c),0);
      for i:=1 to n do
      for j:=1 to n do
      for l:=1 to n do
      c[i,j]:=(c[i,j]+a[i,l]*b[l,j]) mod m;
      b:=c;
    end;
    k:=k div 2;
    fillchar(c,sizeof(c),0);
    for i:=1 to n do
    for j:=1 to n do
    for l:=1 to n do
    c[i,j]:=(c[i,j]+a[i,l]*a[l,j]) mod m;
    a:=c;
  until k=0;
  n:=n div 2;
  for i:=1 to n do
  begin
    for j:=n+1 to n*2 do
    begin
      if i+n=j then
      begin
        if b[i,j]=0 then write(m-1,' ')
        else write(b[i,j]-1,' ');
      end
      else write(b[i,j],' ');
    end;
    writeln;
  end;
end.

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。