E. Inverse Coloring

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--E. Inverse Coloring

题解

高档题,题意大概是构造一个n*n的矩阵,要求满足相邻行与相邻列之间要么完全相同,要么完全相反。且不存在面积大于等于k的子矩阵颜色完全相同。
首先我们可以发现,只要确定了首行和首列即可得到整个矩阵,且最大颜色相同的矩阵为行最大连续颜色乘以列最大连续颜色。则我们dp行最大连续颜色与列最大连续颜色的数量,再分别枚举即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int mod = 998244353;
ll dp[maxn][maxn][2];//λ�ã�������������ɫ��
ll num[maxn];

int main() {
    ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int k = 1; k <= n; k++) {
        memset(dp, 0, sizeof(dp));
        dp[1][1][0] = dp[1][1][1] = 1;
        for (int i = 2; i <= n; i++) {//�
            for (int j = 1; j <= min(i,k); j++) {//��������
                dp[i][1][1] += dp[i - 1][j][0];
                dp[i][1][0] += dp[i - 1][j][1];
                dp[i][j][1] += dp[i - 1][j - 1][1];
                dp[i][j][0] += dp[i - 1][j - 1][0];
                dp[i][1][0] %= mod;
                dp[i][1][1] %= mod;
                dp[i][j][0] %= mod;
                dp[i][j][1] %= mod;
            }
        }
        for (int i = 1; i <= k; i++) {
            num[k] += dp[n][i][0] + dp[n][i][1];
            num[k] %= mod;
        }
    }
    for (int i = n; i >= 2; i--) {
        num[i] = num[i] - num[i - 1] + mod;
        num[i] %= mod;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i*j >= k)break;
            ans += num[i] * num[j];
            ans %= mod;
        }
    }
    if (ans % 2 == 1)ans = (ans + mod) / 2;
    else ans /= 2;
    cout << ans << endl;
}

标签: dp, combinatorics

添加新评论