ARC 补题目录

记录一下自己独立做出的一道状压 DP（状压刚入门）。
注意到 $M$ 非常小，所以考虑状压 DP。

对于对于一个数 $a$，相邻两个 $a$ 之间必须要有 $X_a$。
我们修改一下限制条件：$X_a$ 之后可以填 $a$。
- 对于之前有 $a$ 的情况，填了 $X_a$ 之后填不填 $a$ 都无所谓。
- 对于之前没有 $a$ 的情况，那显然成立。
- 因此这么修改一定是合法的。

观察到 $X$ 数列中可能有数重复出现，所以考虑对每个数记录“它之后能放的数”的集合 $t$。

设状态。$f_{i,S}$ 表示填完 $i$ 个数，要填 $i+1$ 个数（主动转移），可以填的数的集合是 $S$ 的方案数。

初始状态 $f_{0,2^m-1} = 1$，答案是 $ans=\sum_{0}^{2^m-1} f_{n,i}$。

转移显然，枚举第 $i+1$ 位填 $x$，当前的集合是 $j$，方案数累加即可。
可以滚动数组优化的，但是不优化也能过。

对 $998244353$ 取模，翻译没说。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 15, M = (1 << 10) + 15, K = 15;
const int mod = 998244353;
int n, m, t[M];
int f[N][M];

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1, x; i <= m; i++) {
        scanf("%d", &x);
        t[x] |= (1 << i - 1);
    }
    f[0][(1 << m) - 1] = 1;
    for (int i = 0; i < n; i++) {
        for (int x = 1; x <= m; x++)
            for (int j = 0; j < (1 << m); j++) {
                if (j & (1 << x - 1)) (f[i + 1][(j ^ (1 << x - 1)) | t[x]] += f[i][j]) %= mod;
            }
    }
    long long ans = 0;
    for (int i = 0; i < (1 << m); i++) (ans += f[n][i]) %= mod;
    printf("%lld\n", ans);
    return 0;
}