题目分析

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;
    }
};
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注