这道题的难点在于思考dp表示什么

首先可以令ans[len]表示白色子矩阵边长最大值大于等于len的方案数则ans[len]-ans[len+1]就是beautifulness为len的方案数

白色子矩阵边长最大值大于等于len的方案数=总方案-白色子矩阵边长最大值小于len的方案数

经过这样的转化，我们就好dp了，我们先穷举len

令f[i][st]表示到第i行，状态为st的白色子矩阵边长最大值小于len的方案数

怎么设计状态呢，由于要保证白色子矩阵边长最大值小于len

我们维护一个n-len+1的len进制数，第j位表示(i,j)~(i,j+len-1)中向上延伸的白色格子数的最小值

这样我们二进制穷举每行的涂色方法就可以转移状态了

1 #include
      
        2  3 using namespace std; 4 typedef long long ll; 5 const int mo=1e9+7; 6 int d[10],a[10],ans[10],v[10],n; 7 char s[10]; 8 void inc(int &a,int b) 9 {10     a+=b;11     if (a>mo) a-=mo;12 }13 14 struct node15 {16     int st[200010],c[200010],len;17     void clr()18     {19         for (int i=1; i<=len; i++) c[st[i]]=0;20         len=0;21     }22     void push(int nw,int w)23     {24         if (!c[nw]) st[++len]=nw;25         inc(c[nw],w);26     }27 } f[2];28 int main()29 {30     int cas;31     scanf("%d",&cas);32     f[0].len=f[1].len=0;33     while (cas--)34     {35         int m=1;36         scanf("%d",&n);37         for (int i=1; i<=n; i++)38         {39             scanf("%s",s);40             a[i]=0;41             for (int j=0; j
       
        >r)&1) continue;65                         for (int j=0; j
        
         =j&&r
         
          -1) f[p].push(nw,w);80                     }81                 }82             }83             ans[l]=0;84             for (int i=1; i<=f[p].len; i++)85             {86                 int x=f[p].st[i];87                 inc(ans[l],f[p].c[x]);88             }89             ans[l]=(m-ans[l]+mo)%mo;90             ans[l-1]=(ans[l-1]-ans[l]+mo)%mo;91         }92         for (int i=0; i<=n; i++)93             printf("%d\n",ans[i]);94     }95 }