program poj3868;
type
    gj=array [0..101] of longint;
const
    maxn=100000;
var
    o,q,p,r,c,w,i,j,k,x,y:longint;
    now,root:array [0..1,0..301,0..301] of longint;
    change:array [0..301,0..301] of char;
    count,ans:array [0..1,0..90001] of longint;
    ch:char;
    st:string;
    n:gj;

procedure swap (var a,b:longint);inline;
begin
    if a=b then exit;
    b:=a xor b;
    a:=a xor b;
    b:=a xor b;
end;

procedure divide (var a:gj;b:longint;var c:longint);inline;
var
    i:longint;
begin
    for i:=a[0] downto 2 do
        begin
            a[i-1]:=a[i-1]+a[i] mod b * 10;
            a[i]:=a[i] div b;
        end;
    c:=a[1] mod b;
    a[1]:=a[1] div b;
    while (a[0]<>1)and(a[a[0]]=0) do dec(a[0]);
end;

begin
    read(r,c);
    readln(ch,st);
    n[0]:=length(st);
    for i:=1 to n[0] do
        n[n[0]-i+1]:=ord(st[i])-48;
    q:=0;
    for i:=1 to r do
        for j:=1 to c do
            root[0,i,j]:=i*c-c+j;
    for i:=1 to r-1 do
        begin
            for j:=1 to c-1 do
                begin
                    inc(count[0,root[0,i,j]]);
                    read(ch);
                    change[i,j]:=ch;
                    case ch of
                        'R':begin
                                swap(root[0,i,j],root[0,i+1,j]);
                                swap(root[0,i+1,j],root[0,i+1,j+1]);
                                swap(root[0,i+1,j+1],root[0,i,j+1]);
                            end;
                        'L':begin
                                swap(root[0,i,j],root[0,i,j+1]);
                                swap(root[0,i,j+1],root[0,i+1,j+1]);
                                swap(root[0,i+1,j+1],root[0,i+1,j]);
                            end;
                    end;
                end;
            readln;
        end;
    p:=0;
    for i:=1 to r do
        for j:=1 to c do
            now[0,i,j]:=i*c-c+j;
    divide(n,(r-1)*(c-1),w);
    while not ((n[0]=1)and(n[1]=0)) do
        begin
            divide(n,2,o);
            if o = 1 then 
                begin
                    p:=1-p;
                    for i:=1 to r do
                        for j:=1 to c do
                            begin
                                ans[p,now[1-p,i,j]]:=ans[1-p,now[1-p,i,j]]+count[q,i*c-c+j];
                                if ans[p,now[1-p,i,j]]>=maxn then ans[p,now[1-p,i,j]]:=ans[p,now[1-p,i,j]]-maxn;
                            end;
                    for i:=1 to r do
                        for j:=1 to c do
                            begin
                                x:=(root[q,i,j]-1) div c +1;
                                y:=root[q,i,j]-(x-1)*c;
                                now[p,i,j]:=now[1-p,x,y];
                            end;
                end;
            q:=1-q;
            for i:=1 to r do
                for j:=1 to c do
                    begin
                        count[q,root[1-q,i,j]]:=count[1-q,root[1-q,i,j]]+count[1-q,i*c-c+j];
                        if count[q,root[1-q,i,j]]>=maxn then count[q,root[1-q,i,j]]:=count[q,root[1-q,i,j]]-maxn;
                    end;
            for i:=1 to r do
                for j:=1 to c do
                    begin
                        x:=(root[1-q,i,j]-1) div c +1;
                        y:=root[1-q,i,j]-(x-1)*c;
                        root[q,i,j]:=root[1-q,x,y];
                    end;
        end;
    for i:=1 to r-1 do
        if w>0 then
        for j:=1 to c-1 do
            begin
                dec(w);
                inc(ans[p,now[p,i,j]]);
                case change[i,j] of
                    'L':begin
                            swap(now[p,i,j],now[p,i,j+1]);
                            swap(now[p,i,j+1],now[p,i+1,j+1]);
                            swap(now[p,i+1,j+1],now[p,i+1,j]);
                        end;
                    'R':begin
                            swap(now[p,i,j],now[p,i+1,j]);
                            swap(now[p,i+1,j],now[p,i+1,j+1]);
                            swap(now[p,i+1,j+1],now[p,i,j+1]);
                        end;
                end;
                if w=0 then break;
            end;
    for i:=1 to r*c do
        writeln(ans[p,i]);
end.

• Re:常数挂了……但是实在是没什么可优化的……求破 (26) weixinding 2012-05-18 19:59:36