题解：P14599 CF1093F 加强版

喵仔牛奶 · 2025-11-25 07:50:42 · 题解

我本来也打算造个这个题的加强版传主题库来着。

令 m 为题面中的 len。

要刻画极长同色连续段长度 <m，施容斥，钦定若干连续段，然后贡献的系数为这些连续段长度的容斥系数的乘积。

考虑怎么求容斥系数。设容斥系数的生成函数为 F(x)，则：

因此若 n\bmod m=1，系数为 1；若 n\bmod m=0，系数为 -1；否则系数为 0。

如果区间里全是 -1，有 v 种填法；只有一种数，有 1 种填法；否则有 0 种填法。直接 DP，分段转移并前缀和优化即可，复杂度 \mathcal O(n)。

:::info[code]

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define CUP(i, l, r) for (int i = (l); i < (r); ++ i)
#define CDW(i, r, l) for (int i = (r) - 1; i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define memc(x, y) memcpy((x), (y), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
using namespace std;
namespace math { ... }
namespace Milkcat {
    using namespace math::Z;
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e6 + 5;
    int n, k, v, a[N], l[N], b[N]; MI f[N], g[N];
    // g[i]=f[i]+f[i-k]+f[i-k*2]+...
    int L(int x, int y) { return x - (x - y % k + k) % k; }
    int main() {
        cin >> n >> v >> k;
        REP(i, 1, n) cin >> a[i];
        REP(i, 1, n) {
            b[i] = (a[i] < 0 ? b[i - 1] : i);
            l[i] = (a[i] < 0 || a[i] == a[b[i - 1]] ? l[i - 1] : b[i - 1]);
        }
        f[0] = g[0] = 1;
        REP(i, 1, n) {
            auto slv = [&](int t, int c) {
                int x = L(i - 1, t), y = L(b[i] - 1, t), z = L(l[i] - 1, t);
                MI A = (x < 0 ? 0 : g[x]), B = (y < 0 ? 0 : g[y]), C = (z < 0 ? 0 : g[z]);
                f[i] += ((A - B) * v + (B - C)) * c;
            };
            slv(i - 1, 1), slv(i, -1);
            g[i] = f[i] + (i >= k ? g[i - k] : 0);
        }
        cout << f[n] << '\n';
        return 0;
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

:::