CF1585F Non-equal Neighbours 题解

· · 题解

容斥 DP 神仙题 qwq。

考虑容斥，钦定 k 个 i 满足 b_i = b_{i + 1}, \, (1 \le i < n)，记其方案数为 F(k)。

这样，答案即为：

ans = \sum_{k = 0}^{n - 1} (-1) ^ k F(k)

首先有一个转化，钦定 k 个 i 满足 b_i = b_{i + 1}, \, (1 \le i < n)，相当于把 b 数组 unique 后剩下最多 n - k 个元素。

有了这个性质，不难得到一个 O(n ^ 3) 的朴素做法。设 f_{i, j} 表示考虑前 i 个位置，划分成 j 段的方案数。

DP 转移为：f_{i, j} = \sum\limits_{k = 1}^{i - 1} f_{k, j - 1} \times \min\limits_{l = k + 1}^{i} a_l。

但这样复杂度爆炸，怎么办呢？观察转移方程发现一个性质：第二维下标为 j 的所有状态只会由下标为 j - 1 的状态转移得到。而我们最后统计答案时，也只关心 k 的奇偶性来决定容斥系数。于是可以重新设计状态 f_{i, 0 / 1} 表示考虑前 i 个位置，划分成 偶数 / 奇数 段的方案数。

新的转移为：f_{i, j} = \sum\limits_{k = 1}^{i - 1} f_{k, j \oplus 1} \times \min\limits_{l = k + 1}^{i} a_l，其中 \oplus 为异或运算符。

可这样还是 O(n^2) 的。柿子前面是一个前缀和形式，不好优化的是后面 \min 的部分。

若 a_i = \min\limits_{j = 1}^{i} a_j，转移显然有：

f_{i, j} = \sum\limits_{k = 1}^{i - 1} f_{k, j \oplus 1} \times a_i

否则，设 a_i 前面第一个比它小的位置为 p（可以单调栈求出）。我们按照 k 与 p 的关系分类讨论：

综上有：

f_{i, j} = f_{p, j} + \sum\limits_{k = p}^{i - 1} f_{k, j \oplus 1} \times a_i

用前缀和优化即可做到 O(1) 转移。

最后，若 n 为偶数，n - k 的奇偶性同 k 的奇偶性，答案为 f_{n, 0} - f_{n, 1}。反之为 f_{n, 1} - f_{n, 0}。

时间复杂度为 O(n)。

Code

#include <cstdio>
#include <stack>
typedef long long ll;
const int n_max = 2e5 + 5;
const ll mod = 998244353;
int a[n_max], n;
ll f[n_max][2], g[n_max][2];
std::stack<int> stk;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    f[0][0] = g[0][0] = 1ll;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && a[stk.top()] >= a[i])
            stk.pop();
        if (stk.empty()) {
            for (int j : {0, 1})
                f[i][j] = g[i - 1][j ^ 1] * a[i] % mod;
        } else {
            for (int j : {0, 1})
                f[i][j] = (f[stk.top()][j] + (g[i - 1][j ^ 1] - g[stk.top() - 1][j ^ 1]) * a[i] % mod) % mod;
        }
        for (int j : {0, 1})
            g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
        stk.push(i);
    }
    int sgn = (n & 1) ? -1 : 1;
    printf("%lld\n", ((f[n][0] - f[n][1]) * sgn % mod + mod) % mod);
    return 0;
}