自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 23:10:51，当前版本为作者最后更新于2025-03-05 19:01:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么还搬 ARC 原题啊？泪目了。

直接做容易算重，考虑正难则反，求有多少个序列没有妙手。

$X,Y,Z$ 都非常小，考虑状压，$f_{n,S}$ 表示前 $n$ 个数，$x\in S$ 表示存在一个后缀和为 $x$。

妙手代表的状态即为 $\{z,y+z,x+y+z\}$，不向包含这个状态的 $S$ 转移即可，复杂度为 $\mathcal O(nV2^{X+Y+Z})$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 998244353;
int n, m, x, y, z, e, ans = 1, f[41][1 << 17];
int main() {
	cin >> n >> x >> y >> z, m = (1 << (x + y + z)) - 1, e = (1 << (z - 1)) | (1 << (y + z - 1)) | (1 << (x + y + z - 1));
	f[0][0] = 1;
	for (int i = 1; i <= n; i++, ans = ans * 10ll % p) {
		for (int j = 0; j <= m; j++) {
			for (int k = 1; k <= 10; k++) {
				int s = ((j << k) | (1 << (k - 1))) & m;
				if ((s | e) != s) f[i][s] = (f[i][s] + f[i - 1][j]) % p;
			}
		}
	}
	for (int i = 0; i <= m; i++) ans = (ans + p - f[n][i]) % p;
	cout << ans << '\n';
}