学步园

【题意】

有n只兔子，有如下三种操作

g i：给兔子i一颗花生

e i：让兔子i把花生吃完

s i j：将兔子i和兔子j的花生交换

初始兔子都没有花生，求m轮交换后各个兔子有多少花生

【输入】

多组数据，数据以一行三个0结束

每组数据第一行n、m、k

接下来k行每行一个操作

【输出】

对于每组数据，输出n个数表示m轮操作后兔子的数量

这个m很大，还要输出所有兔子的情况，很容易联想到矩阵

怎么搞转移矩阵呢，发现只有加1比较难为人

这个我们加一只虚拟兔子0就好了

初始矩阵为单位矩阵

给兔子i一颗花生就是将(i,0)加一

让兔子吃完花生就是将兔子所对的一行清空

交换就是将兔子对应的两行交换

然后快速幂搞一搞就好了

program poj3735;
type
  arr=array [0..100] of int64;
  square=array [0..100] of arr;
var
  n,m,k,i,j:longint;
  ans,root:square;
  order:char;

procedure swap (var a,b:arr);
var
  i:arr;
begin
  i:=a;
  a:=b;
  b:=i;
end;

function matrixmul (a,b:square):square;
var
  i,j,k:longint;
  ans:square;
begin
  fillchar(ans,sizeof(ans),0);
  for i:=0 to n do
    for k:=0 to n do
      if a[i,k]<>0 then
        for j:=0 to n do
          ans[i,j]:=ans[i,j]+a[i,k]*b[k,j];
  exit(ans);
end;

function power (m:longint):square;
var
  ans,now:square;
  i:longint;
begin
  fillchar(ans,sizeof(ans),0);
  if m=0 then exit(ans);
  for i:=0 to n do
    ans[i,i]:=1;
  now:=root;
  while m<>0 do
    begin
      if m and 1 = 1 then ans:=matrixmul(ans,now);
      m:=m div 2;
      now:=matrixmul(now,now);
    end;
  exit(ans);
end;

begin
  repeat
    readln(n,m,k);
    if (n=0)and(m=0)and(k=0) then break;
    fillchar(root,sizeof(root),0);
    for i:=0 to n do
      root[i,i]:=1;
    while k>0 do
      begin
        dec(k);
        read(order);
        case order of
          'g':begin
                read(i);
                inc(root[i,0]);
              end;
          'e':begin
                read(i);
                root[i]:=root[0];
                root[i,0]:=0;
              end;
          's':begin
                read(i,j);
                swap(root[i],root[j]);
              end;
        end;
        readln;
      end;
    ans:=power(m);
    for i:=1 to n do
      write(ans[i,0],' ');
    writeln;
  until false;
end.