题目概述

有 $n\times n$ 的矩阵，现在给矩阵黑白染色，需要满足相邻行和相邻列要么全相同要么全不同，还需要满足最大同色子矩阵的面积小于 $K$ ，求方案数。

解题报告

行列同时满足一看就不可做啊，我们分析(yy)一波会发现行满足列肯定满足，所以不用管列。

然后由于相邻行全要相同或不同，所以可以看做和第一行全相同或全不同。

那么我们需要处理出第一行最大连续长度为 $j$ 的方案数 $g_{j}$ ，定义 $f_{i,j,k}$ 表示已经确定了 $i$ 个格子，目前有 $j$ 个连续相同颜色的格子，最大连续相同颜色的格子数为 $k$ 的方案数，然后 $g_j=\sum_{i=0}^{n}f_{n,i,j}$ 。

统计答案的话只需要枚举 $i$ 表示最大连续相同颜色的格子数，那么下面和第一行相同或者和第一行不同的连续行数都不能超过 $\lfloor{K\over i}\rfloor$ ，这个也可以写DP……等等！这不是和之前的问题一模一样吗……只不过由于第一行确定所以方案数为 $g_j\over 2$ …… $\sum_{i=1}^{n}\sum_{j=1}^{\lfloor{K\over i}\rfloor}{g_ig_j\over 2}$ 就是答案。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=500,MOD=998244353,INV2=MOD+1>>1;

int n,K,f[2][maxn+5][maxn+5],g[maxn+5],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);f[0][0][0]=1;
    for (int i=1,c=1;i<=n;i++,c^=1)
        for (int j=(memset(f[c],0,sizeof(f[c])),0);j<=n;j++)
            for (int k=0;k<=n;k++){
                AMOD(f[c][j+1][max(k,j+1)],f[c^1][j][k]);
                AMOD(f[c][1][max(k,1)],f[c^1][j][k]);
            }
    for (int j=0;j<=n;j++) for (int k=0;k<=n;k++) AMOD(g[k],f[n&1][j][k]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n&&i*j<K;j++)
            AMOD(ans,(LL)g[i]*g[j]%MOD*INV2%MOD);
    return printf("%d\n",ans),0;
}