22 条题解
-
-1voyagec2 LV 10 @ 2009-07-21 08:07:37
现在A的两人交的都是一样的程序
希望不要再看到
没有意义的 -
-22013-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.