位运算是直接对整数在内存中的二进制位进行操作比如.PPTVIP

位运算基本应用 本题性质 性质1：如果n,m都是奇数，则无解，否则有解。 性质2：对于每一次地板，只会影响所铺的上下两行。 性质3：如果按行铺地板，每一行的铺法都类似。 位运算基本应用 可以看出，在按行铺的过程中，某些砖会分成两半，但最多也是向下突出一格，如果将上行空隙填满，则又转移到了下一种状态。 思考：状态如何表示 位运算基本应用 F[I,j]表示当前放满前i行，对应该行的放置状态为j的方案总数: F[I,j]=sum(f[i-1,k]) 状态k为与状态j兼容的第i-1行的状态 初始值？ 最后答案？ 核心代码 for i:=2 to n do for j:=1 to p do begin for k:=1 to q do if (now[j] 兼容 next[k]) then f[i,j]:=(f[i,j]+f[i-1,k]) mod p; end; 实现代码举例 预处理出所有可行的状态 Now[i] :0111 Now[i-1] :1110 Next[i-1]:1000 Now[i] :0111 Now[i-1] :1011 Next[i-1]:1000 状态处理（doit） 处理每种状态当前行的摆放状况（now）和它对下一行的影响（next）。此时需要用到状态压缩，即用二进制表示每一个是否已经被覆盖。 procedure doit; var i:longint; begin l:=l+1; now[l]:=0;next[l]:=0; for i:=1 to m do begin if x[i]=1 then next[l]:=next[l]+(1 shl (i-1)); if x[i]0 then now[l]:=now[l]+(1 shl (i-1)); end; end; procedure dfs(v:longint); begin if v=m+1 then //一行结束，处理 begin doit; exit; end; if v=1 then //第一格 begin x[v]:=1;dfs(v+1); //第一格竖放开始 x[v]:=0;dfs(v+1); //第一格不放 if m1 then begin x[v]:=3; //第一格横放开始 dfs(v+1); end; end else begin if x[v-1]=3 //前一格横放开始 then begin x[v]:=4; //当前格横放结束 dfs(v+1); end else begin x[v]:=1; //当前任意格竖放开始 dfs(v+1); x[v]:=0; //当前任意格不放 dfs(v+1); if v+1=m then begin x[v]:=3; //当前任意格横放开始 dfs(v+1); end; end; end; end; 状态转移 i表示行数，j表示当前行状态，k表示上一行状态 for i:=2 to n do for j:=1 to l do begin for k:=1 to l do if (now[j] xor next[k])+1=1 shl m then f[i,j]:=(f[i,j]+f[i-1,k]) mod p; end; k:=0; for i:=1 to l do if next[i]=0 then k:=(k+f[n,i]) mod p; writeln(k); 压位DP 例3、炮兵阵地 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮