直接硬嗯是困难的，因此考虑正难则反计算有多少组不合法的方案数，然后用总方案数减去之。总方案数是容易计算的，显然就是 。
考虑 dp 计算出不合法方案数。看到 想到状压。设 表示当前考虑了前 个数，以第 个数为结尾的所有后缀可以表示出的值的状态为 不合法组数的方案数。这样做的正确性在于合法状态不能在后缀部分添加一段数使得其再次变得不合法。
直接做第二维很爆炸，但是 因此只需要记录 以内的数是否可以存储出即可。此时状态的空间复杂度正确。考虑转移。
对于一个状态 ，考虑枚举 ，那么 集合内所有可以表示的元素的值都会增加 ，只需要把 整体左移 位，然后单独添加出只包含 元素的后缀和 即可。设这个状态为 ，则转移即为：。
答案计算就是 ，这个部分比较显然。总时间复杂度为 ，其中 为 序列中元素的值域即 ，可以通过。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
const int mod = 998244353;
int f[44][1 << 18];
inline void add(int &x, int v) {
x = (x + v) % mod;
}
signed main() {
int n, x, y, z;
cin >> n >> x >> y >> z;
f[0][0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = 0; j < (1 << (x + y + z)); ++j)
for (int k = 1; k <= 10; ++k) {
int state = ((j << k) | (1 << (k - 1))) & ((1 << (x + y + z)) - 1);
if ((~state >> (z - 1) & 1) || (~state >> (y + z - 1) & 1) || (~state >> (x + y + z - 1) & 1)) add(f[i][state], f[i - 1][j]);
}
int cnt = 1;
for (int i = 0; i < n; ++i) cnt = cnt * 10 % mod;
for (int i = 0; i < (1 << (x + y + z)); ++i) cnt = (cnt + mod - f[n][i]) % mod;
cout << cnt << '\n';
return 0;
}
喜欢的话，留下你的评论吧～