Rockdu's Blog

Board of size $1\times 1$ is either a single black tile or a single white tile. Both of them include a rectangle of a single color, consisting of $1$ tile.

Here are the beautiful colorings of a board of size $2\times 2$ that don't include rectangles of a single color, consisting of at least $3$ tiles:

The rest of beautiful colorings of a board of size $2\times 2$ are the following

 小清新dp题，首先我们发现只要对于一个方向满足了条件，那么另一个方向一定满足条件。

然后我们考虑纯色矩形大小的限制，可以先处理出f(i)表示最长有i个连续格子的列有多少种，这个可以O(n^3) dp得到，然后我们再横着摆放这些列，因为要满足限制，所以假如当前放的列上最大的矩形为i，不能连续n/i列都不反色。最后总复杂度O(n^3)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int mod = 998244353;
const int maxn = 5e2 + 5;

int now, n, Mx;
int dp[2][maxn][maxn];
int g[maxn];

void Add(int & a, const int &b) {
	a += b;
	if(a > mod) a -= mod;
}

int main() {
	scanf("%d%d", &n, &Mx);
	dp[now][1][1] = 2;
	For(i, 1, n - 1) {
		memset(dp[now ^ 1], 0, sizeof(dp[now ^ 1]));
		For(j, 1, i + 1) For(k, 1, i + 1) {
			Add(dp[now ^ 1][j + 1][max(j + 1, k)], dp[now][j][k]);
			Add(dp[now ^ 1][1][k], dp[now][j][k]);
		}
		now ^= 1;
	}
	For(j, 1, n) For(k, 1, n)
		Add(g[k], dp[now][j][k]);
	memset(dp, 0, sizeof(dp)), now = 0;
	For(i, 1, n) if(i < Mx) dp[now][1][i] = g[i];
	For(i, 1, n - 1) {
		memset(dp[now ^ 1], 0, sizeof(dp[now ^ 1]));
		For(j, 1, i + 1) 
			For(k, 1, n) {
				//cout << i << " " << j << " " << k << " " << dp[now][j][k] << endl;
				if((j + 1) * k < Mx) {
					Add(dp[now ^ 1][j + 1][k], dp[now][j][k]);
					//cout << i << " " << j << " " << k << "-" << dp[now][j][k] << ">" << i + 1 << " " << j + 1 << " " << k << endl;
				}	
				//cout << i << " " << j << " " << k << "-" << dp[now][j][k] << ">" << i + 1 << " " << 1 << " " << k << endl;
				Add(dp[now ^ 1][1][k], dp[now][j][k]);
			}
		now ^= 1;
	}
	int ans = 0;
	For(j, 1, n) 
		For(k, 1, n)
			Add(ans, dp[now][j][k]);
	printf("%d", ans);
	return 0;
}