CF1943D1 Counting Is Fun (Easy Version) - Solution

strcmp · 2024-09-30 17:41:38 · 题解

这是积木大赛，所以如果没有 l < r 的限制我们一定有解。

但是有 l < r 的限制，就要看它产生了什么限制。

对，就是这种类似 CF Logo 的图形。

翻译成人话就是：存在 i 满足 a_i > a_{i - 1} + a_{i + 1}，则必定无解。

首先无解是一定的，这种情况下 a_i 最多减 a_{i - 1} + a_{i + 1} 次，然后 a_{i - 1} 和 a_{i + 1} 变成 0，就消不了了。

那不存在这种情况就合法了吗？这也是容易理解的。

根据积木大赛的结论，我们考虑包含 a_{i - 1} 的所有区间 [?,\,i - 1]，我们显然不关心 ? 是什么。然后考虑将这个区间多覆盖到 i。进而还剩下 a_{i}' = a_{i} - a_{i - 1}。如果 a_{i + 1} - a_i' \ge 0 显然能消完 a_i（把包含 a_{i + 1} 的区间左端点扩到 a_i 就好了）。对所有 a_i 从外到内这样讨论可知必然有解。

好，现在就是计数所有满足 a_{i} \ge a_{i - 1} - a_{i - 2} 的序列方案数了。

此时有一个 naive 的做法就是设个 f_{i,\,x,\,y} 代表前 i 个位置 i 位置是 x 而 i - 1 位置是 y 的方案数。朴素实现 \Theta(nk^3)，后缀和优化一下 \Theta(nk^2)。后者能过 Easy Version。

但还是不够切这道题。

从转移方程上找东西显然是无用功，只能继续发掘性质。比如——考虑容斥。

发现一个重要性质：不合法的位置不会相邻。

很简单，因为你随便考虑某两个相邻的不合法位置，假设分别是 a_{i - 1} 和 a_i。

则 a_{i - 1} > a_{i - 2} + a_{i},\,a_{i} > a_{i - 1} + a_{i + 1} \Rightarrow a_{i} > a_{i} + a_{i - 2} + a_{i + 1} \Rightarrow a_{i - 2} + a_{i + 1} < 0。显然矛盾。

不合法位置不相邻，给我们优化复杂度以极大方便。

一个明显的好处就是我们可以直接从 i - 2 位置转移过来。进而不用考虑 i - 3 选取了什么。

设 f_{i,\,j} 代表考虑到第 i 个数，末尾是 j 的合法序列数。

则有：

因为 i 不合法所以我们不用考虑 i - 1 不合法的可能。后面一项相当于计数 i 位置之前都合法，而 i 位置不合法的序列并容斥。

前面一坨直接记录和，后面一坨倒序枚举 j 前缀和记录 k - j - x 的增量即可。

时间复杂度 \Theta(nk)，可以通过。

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
using ld = double;
typedef long long int ll;
using pdi = pair<ld, int>;
using vec = vector<int>;
constexpr int maxn = 3e3 + 10; 
int T, n, k, mod, f[maxn][maxn], g[maxn][maxn];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &k, &mod);
        rep(i, 0, n + 1) rep(j, 0, k) f[i][j] = g[i][j] = 0;
        f[0][0] = 1; rep(i, 0, k) f[1][i] = g[0][i] = 1, g[1][i] = i + 1;
        rep(i, 2, n + 1) {
            int s = 0;
            per(j, k, 0) f[i][j] = ((ll)g[i - 1][k] - (s = (s + g[i - 2][k - j - 1]) % mod) + mod) % mod;
            rep(j, 0, k) g[i][j] = ((j ? g[i][j - 1] : 0) + f[i][j]) % mod;
        }
        printf("%d\n", f[n + 1][0]);
    }
    return 0;
}

同类题（lca 长训营入营测试赛，侵删）：给定长度为 n 的非负整数序列 w。定义一个长度为 n 的序列 a 的权值是 \prod\limits_{i = 1}^{n - 2} w_{\max \{ a_i,\,a_{i + 1},\,a_{i + 2}\}}，求所有值域在 [0,\,n] 长度为 n 的非负整数序列的权值和。对 998244353 取模，n \le 4 \times 10^3。