题解

22 条题解

  • -1
    @ 2009-07-21 08:07:37

    现在A的两人交的都是一样的程序

    希望不要再看到

    没有意义的

  • -2
    @ 2013-08-12 23:46:14

    A的不容易 放个代码 仅供参考(抄袭慎重)

    const
    maxmod=19901013;
    var
    f:array [0..1,0..65536] of longint;
    power:array [0..16] of longint;
    map:array [0..16,0..16] of char;
    s:array [0..16,0..16,0..16,0..16] of int64;
    g:array [0..16] of int64;
    c:array [0..16] of longint;
    n,m,pre,now:longint; ans:int64;
    //////////////////////////////////////////////////////////////
    procedure init;
    var
    i,j:longint;
    begin
    fillchar(s,sizeof(s),0);
    readln(n,m);
    for i:=1 to n do
    begin
    for j:=1 to m do
    read(map[i,j]);
    readln;
    end;
    end;
    //////////////////////////////////////////////////////////////
    procedure get_power;
    var
    i:longint;
    begin
    power[0]:=1;
    for i:=1 to 16 do power[i]:=power[i-1]*2;
    end;
    //////////////////////////////////////////////////////////////
    procedure CT_dp;
    var
    l,r,u,d,i,j,k,p,x,y,len,kk,dp:longint;
    begin
    for l:=1 to m do
    for r:=l to m do
    for u:=1 to n do
    begin
    pre:=0; now:=1; fillchar(f[pre],sizeof(f[pre]),0); f[pre,0]:=1;
    for d:=u to n do
    for i:=l to r+1 do
    begin
    fillchar(f[now],sizeof(f[now]),0);
    len:=r-l+1; j:=i-l+1;
    if i=r+1 then s[u,l,d,r]:=f[pre,0];
    for p:=0 to 1 shl (len+1)-1 do
    if f[pre,p]<>0 then
    begin
    if i=r+1 then
    begin
    if p mod 2<>0 then continue;
    f[now,p div 2]:=(f[now,p div 2]+f[pre,p]) mod maxmod;
    continue;
    end;
    x:=(p div power[len-j+1]) mod 2;
    y:=(p div power[len-j]) mod 2;
    if map[d,i]='x' then
    begin
    if (x=0) and (y=0) then f[now,p]:=(f[now,p]+f[pre,p]) mod maxmod;
    continue;
    end;
    if (x=0) and (y=0) then
    begin
    f[now,p]:=(f[now,p]+f[pre,p]) mod maxmod;
    kk:=p or power[len-j+1];
    f[now,kk]:=(f[now,kk]+f[pre,p]) mod maxmod;
    kk:=p or power[len-j];
    f[now,kk]:=(f[now,kk]+f[pre,p]) mod maxmod;
    continue;
    end;
    if (x=0) and (y=1) then
    begin
    kk:=p and (not power[len-j]);
    f[now,kk]:=(f[now,kk]+f[pre,p]) mod maxmod;
    continue;
    end;
    if (x=1) and (y=0) then
    begin
    kk:=p and (not power[len-j+1]);
    f[now,kk]:=(f[now,kk]+f[pre,p]) mod maxmod;
    continue;
    end;
    end;
    pre:=1-pre; now:=1-now;
    end;
    end;
    end;
    //////////////////////////////////////////////////////////////
    procedure main;
    var
    i,j,k,tot,p:longint; t:int64;
    begin
    for i:=0 to 1 shl (m-1)-1 do
    begin
    c[0]:=0; tot:=0;
    for j:=1 to m-1 do if (i div power[m-1-j]) mod 2=1 then begin inc(tot); c[tot]:=j; end;
    inc(tot); c[tot]:=m; g[0]:=1;
    for j:=1 to n do
    for k:=0 to j-1 do
    begin
    t:=1;
    for p:=1 to tot do t:=(t*s[k+1,c[p-1]+1,j,c[p]]) mod maxmod;
    if k=0 then g[j]:=t else g[j]:=(g[j]-g[k]*t) mod maxmod;
    end;
    if tot mod 2=1 then ans:=ans+g[n] else ans:=ans-g[n];
    ans:=ans mod maxmod;
    end;
    writeln((ans+maxmod) mod maxmod);
    end;
    //////////////////////////////////////////////////////////////
    begin
    init;
    get_power;
    CT_dp;
    main;
    end.

信息

ID
1581
难度
7
分类
动态规划 | 状态压缩DP 点击显示
标签
递交数
225
已通过
49
通过率
22%
被复制
2
上传者