题目分析

Topcoder 的题太神奇了，要是不写题解，估计下一次遇见就不会做了……

假设我已经随意地点亮了一些格子，那么现在我只要用两个矩形能够盖住所有点亮的格子，就说明方案合法。

用所有亮格子中最左，最右，最上，最下的四个格子确定一个矩形区域，那么这两个矩形用（一个放左上角一个放右下角）（一个放左下角一个放右下角）两种方案都无法覆盖所有亮格子的话，说明该方案一定不合法。

于是只有这个矩形区域的尺寸决定了填它的方案数，枚举尺寸（$O(nm)$），统一处理原网格图中所有该尺寸的矩形区域。

接下来看这个矩形区域，要满足的条件是：

1. （最上一行），（最下一行），（最左一列），（最右一列）各要有一个亮格子
2. （不在左下角 $x * y$区域且不在右上角 $x * y$区域内的格子）和（不在左上角 $x * y$区域且不在右下角 $x * y$区域内的格子）中至少有一个没有亮格子

世界是风云变幻，复杂多样的，一个格子，它可以既是最上的格子，也是最下的格子，也是最左的格子，情况很多……但不会超过 $2^6$种情况！

上面的条件中所有被括号括起来的都称为一条性质，将每个格子的性质集合用一个二进制串表示，然后统计性质集合为 $S$的格子有 $js(S)$个。

DP，$f(zt,k)$表示考虑完了性质集合为 $[0,zt)$的格子的点亮情况，点亮了的格子拥有的性质的并集为 $k$，若继续操作，将整个矩形区域都考虑完点不点亮，能有多少种方案。

初始：$f(2^6,1+2+4+8)=f(2^6,15+16)=f(2^6,15+32)=1$

DP 时，考虑到性质集合 $i$，点亮至少一个性质集合为 $i$的格子有 $2^{js(i)}-1$种方案，一个都不点亮有 $1$种方案，所以 $f(i,k)=f(i+1,k)+(2^{js(i)}-1)f(i+1,k|i)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
const int mod=1000000007;
int n,m,X,Y,ans;
int f[65][65],id[43][43],js[64],bin[1605];

int qm(int x) {return x>=mod?x-mod:x;}
int work(int n,int m) {
    for(RI i=1;i<=n;++i)
        for(RI j=1;j<=m;++j) id[i][j]=0;
    for(RI i=0;i<64;++i) js[i]=0;
    for(RI i=1;i<=n;++i) id[i][1]|=1,id[i][m]|=2;
    for(RI i=1;i<=m;++i) id[1][i]|=4,id[n][i]|=8;
    for(RI i=1;i<=n;++i)
        for(RI j=1;j<=m;++j) {
            if(!((i<=X&&j<=Y)||(i>=n-X+1&&j>=m-Y+1))) id[i][j]|=16;
            if(!((i<=X&&j>=m-Y+1)||(i>=n-X+1&&j<=Y))) id[i][j]|=32;
            ++js[id[i][j]];
        }
    f[64][15]=f[64][31]=f[64][47]=1;
    for(RI i=63;i>=0;--i) {
        for(RI hav=0;hav<64;++hav) {
            f[i][hav]=1LL*qm(bin[js[i]]-1+mod)*f[i+1][hav|i]%mod;
            f[i][hav]=qm(f[i][hav]+f[i+1][hav]);
        }
    }
    return f[0][0];
}
class LitPanels{
    public:
    int countPatterns(int kn,int km,int kX,int kY) {
        n=kn,m=km,X=kX,Y=kY,ans=1;
        bin[0]=1;for(RI i=1;i<=n*m;++i) bin[i]=qm(bin[i-1]+bin[i-1]);
        for(RI i=1;i<=n;++i)
            for(RI j=1;j<=m;++j)
                ans=qm(ans+1LL*work(i,j)*(n-i+1)%mod*(m-j+1)%mod);
        return ans;
    }
};