题解:P11856 [CSP-J2022 山东] 吟诗

· · 题解

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

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

妙手代表的状态即为 $\{z,y+z,x+y+z\}$,不向包含这个状态的 $S$ 转移即可,复杂度为 $\mathcal O(nV2^{X+Y+Z})$。 ```cpp #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'; } ```