Codeforces 1027E(DP+乘法原理)

Codeforces 1027E
题意:给出一个正方形,要求在每个位置涂上黑/白色,要求满足:任意相邻的两行,其颜色要么完全相同,要么完全相反。任意相邻的两列,其颜色也要么相同要么完全相反。
且这个矩形中,不存在任意一个大小大于等于$k$的同色矩形。

对于”满足:任意相邻的两行,其颜色要么完全相同,要么完全相反。任意相邻的两列,其颜色也要么相同要么完全相反。”,也就是说只要确定正方形一行一列,整个正方形都被确定。
那么我们设确定的行的黑白情况是$a_i$, 列是$b_i$,对于$(i,j)$的颜色即为$a_i xor b_i$
那么我们就考虑如何满足不存在任意一个大小大于等于$k$的同色矩形。
显然就是$a_i$最大连续的一段和$b_i$最大连续的一段的乘积不能大小大于等于$k$。
那么我们用 DP 求出序列上最大连续的一段为$x$的方案数就可以用乘法原理做了。但是发现这个状态并不容易求,那么我们就求序列上最大连续的一段小于等于$x$的方方案,对于等于,就是$dp(i)-dp(i-1)$算出来。
所以设$dp(i,j)$为前$i$个数最大连续的一段为$j$的方案数。那么$dp(i,j)=dp(i-k,j), 1 \leq k \leq min(i,j)$
然后统计答案就可以了。

知识点:要善于发掘题目条件对解题的限制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
const LL MAXN = 505, MO = 998244353;
LL n, K, dp[MAXN][MAXN], ans[MAXN];
void clean() {
}
int solve() {
clean();
for (LL i = 1; i <= n; i++) {
dp[i][0] = 1;
for (LL j = 1; j <= n; j++)
for (LL k = 1; k <= std::min(i, j); k++) dp[i][j] = (dp[i][j] + dp[i][j - k]) % MO;
}
for (LL i = 1; i <= n; i++) ans[i] = (dp[i][n] - dp[i - 1][n] + MO) % MO;
LL ret = 0;
for (LL i = 1; i <= n; i++)
for (LL j = 1; j <= n; j++) if (i * j < K) ret = (ret + (ans[i] * ans[j]) % MO) % MO;
printf("%lld\n", (ret * 2ll) % MO);
return 0;
}
int main() {
scanf("%lld%lld", &n, &K), solve();
return 0;
}
------ 本文结束 ------