voj 1049クリスマスイブへのギフトマトリクス高速べき乗

順次m個の置換を与え、このm個の置換を繰り返して初期シーケンスを操作し、k回の置換後のシーケンスを尋ねる.m<=10, k<2^31.
解析:置換ごとにn*nの行列を構築し,そのm個の行列の積を求めて行列Aと表記し,A^k div mを算出し,型取り後のいくつかの変換を処理すればよい.
コード:

type
  arr=array[1..100,1..100] of longint;

var
  n,m,p,i,j,x:longint;
  c,d:arr;
  f:array[1..10] of arr;

procedure chengd(a,b:arr);
var
  i,j,k:longint;
begin
  fillchar(d,sizeof(d),0);
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        d[i,j]:=d[i,j]+a[i,k]*b[k,j];
end;

procedure chengc(a,b:arr);
var
  i,j,k:longint;
begin
  fillchar(c,sizeof(c),0);
  for i:=1 to n do
    for j:=1 to n do
      for k:=1 to n do
        c[i,j]:=c[i,j]+a[i,k]*b[k,j];
end;

procedure ksm(x:longint);
begin
  if x=0 then exit;
  ksm(x div 2);
  chengc(c,c);
  if x mod 2=1 then chengc(c,d);
end;

begin
  readln(n,m,p);
  for i:=1 to m do
    for j:=1 to n do
    begin
      read(x);
      f[i,x,j]:=1;
    end;
  for i:=1 to n do
  begin
    d[i,i]:=1;
    c[i,i]:=1;
  end;
  for i:=1 to m do
    chengd(d,f[i]);
  ksm(p div m);
  for i:=1 to p mod m do
    chengc(c,f[i]);
  for i:=1 to n do
    for j:=1 to n do
      if c[j,i]=1 then
      begin
        write(j,' ');
        break;
      end;
end.