题目链接：HDU 6578

有 $n$ 个格子排成一行，从左往右标号为 $1$ 到 $n$。

Tom 想要将每个格子填上 $\{0, 1, 2, 3\}$ 中的一个数字。但是他有 $m$ 条限制：第 $i$ 条限制为区间 $[l_i, r_i]$ 中必须有恰好 $x_i$ 种不同的数字。

请你求出满足所有限制的填数字的方案数量，答案对 $998244353$ 取模。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 15$，$1 \le n \le 100$，$0 \le m \le 100$，$1 \le l_i \le r_i \le n$，$1 \le x_i \le 4$。

Solution

昨天刚在 Codeforces 上做了一道染色题今天又来一道……

发现数字本身是没有意义的，这样状态设计起来就比较方便。我们考虑到当前位置，数字 $0, 1, 2, 3$ 上一次出现的位置分别为 $p_0, p_1, p_2, p_3$，由于数字本身可以认为是「无序」的，于是我们将 $p_0, p_1, p_2, p_3$ 从大到小排序后得到 $i, j, k, l$，即状态 $f(i, j, k, l)$ 表示考虑到当前位置 $i$ 的方案数。

转移方程只需要考虑第 $i +1$ 个位置的数字和 $i, j, k, l$ 中哪一者相同，在此略去。

接下来考虑如何处理限制条件。我们将 $m$ 条限制按照右端点分类，对于当前位置 $i$ 的状态 $f(i, j, k, l)$，我们枚举所有右端点为 $i$ 的限制，如果不满足则将 $f(i, j, k, l)$ 的值改为 $0$。

时间复杂度：$\mathcal O(T(m + n ^ 4))$，带有 $\frac{1}{24}$ 的常数。

Code

#include <cstdio>
#include <cstring>
#include <vector>

const int N = 1e2 + 5;
const int MOD = 998244353;

int T, n, m, f[N][N][N];
std::vector<std::pair<int, int> > vec[N];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; cs++)  {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) vec[i].clear();
        for (int i = 1, l, r, x; i <= m; i++) {
            scanf("%d%d%d", &l, &r, &x);
            vec[r].emplace_back(std::make_pair(l, x));
        }
        memset(f, 0, sizeof(f));
        f[0][0][0] = 1;
        for (int t = 0; t < n; t++) {
            static int g[N][N][N];
            for (int i = 0; i <= t; i++) {
                for (int j = 0; j <= i; j++) {
                    for (int k = 0; k <= j; k++) {
                        g[i][j][k] = 0;
                    }
                }
            }
            for (int i = 0; i <= t; i++) {
                for (int j = 0; j <= i; j++) {
                    for (int k = 0; k <= j; k++) {
                        if (f[i][j][k] == 0) continue;
                        add(g[i][j][k], f[i][j][k]);
                        add(g[t][i][j], f[i][j][k]);
                        add(g[t][i][k], f[i][j][k]);
                        add(g[t][j][k], f[i][j][k]);
                    }
                }
            }
            for (int i = 0; i <= t; i++) {
                for (int j = 0; j <= i; j++) {
                    for (int k = 0; k <= j; k++) {
                        for (std::pair<int, int> x : vec[t + 1]) {
                            if (1 + (i >= x.first) + (j >= x.first) + (k >= x.first) != x.second) {
                                g[i][j][k] = 0;
                                break;
                            }
                        }
                        f[i][j][k] = g[i][j][k];
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                for (int k = 0; k <= j; k++) {
                    add(ans, f[i][j][k]);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}