题意

已知一个 $n\times n$ 的方板，你可以对每个格子染黑色或者白色。

如果同时满足下面两个条件，那么这种染色就是漂亮的：

• 相邻两行的染色方法 相同 或者 完全相反。

• 相邻两列的染色方法 相同 或者 完全相反。

如果一种染色是漂亮的，且在这种染色中最大同色子矩阵小于 $k$，那么就是完美的染色。

求完美染色的方案数。

题解

容易发现如果我们确定了一行，那么下面每行都是要么完全相同，要么相反。

所以如果我们确定了第一行和第一列的染色方法，那么整个方板的染色就都可以确定。

然后可以发现最大同色子矩阵实际就是第一行的最大同色子串长度乘以第一列的最大同色子串长度。

设 $f_{i,j}$ 表示当前总长度为 $i$，最大同色子串为 $j$ 的方案数。

考虑最后一段的长度，分两种情况讨论。

• 最后一段的长度 $k<j$，那么 $f_{i,j}+=f_{i-k,j}$

• 最后一段长度等于 $j$，那么$f_{i,j}+=\sum_{k=0}^j f_{i-j,k}$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505,mod=998244353;
int f[N][N],n,K,ans;
void add(int &x,int y){x=(x+y)%mod;}
int main(){
    scanf("%d%d",&n,&K);
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        f[i][i]=1;
        for(int j=1;j<i;j++){
            for(int k=1;k<j;k++)add(f[i][j],f[i-k][j]);
            for(int k=0;k<=j;k++)add(f[i][j],f[i-j][k]);
        }
    }
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i*j<K)add(ans,1ll*f[n][i]*f[n][j]%mod);
    printf("%d",ans*2ll%mod);
    return 0;
}

上面的代码其实可以通过前缀和优化到 $O(n^2)$。