AGC073A - Chords and Checkered

· · 题解

关键词：计数的是被翻转了奇数次的区域个数；某 x 条弦恰好对应唯一一个被翻转了 x 次的区域。

考虑染色操作的实质，其实是从一个全白的圆开始，然后每次我们选择一条弦围成的区域，将这块区域内颜色翻转，最后答案就是黑色区域个数。

那么对于一个区域，如果被翻转了奇数次，显然就是黑色，否则就是白色。所以实际上我们计数的是被翻转了奇数次的区域个数。

一个奇数次的区域分为两种情况，一种是只被翻转了 1 次，另一种是被翻转了 3 次及以上的奇数次。

考虑只被翻转了 1 次怎么做：在一个合法的情况中，某 x 条弦恰好对应唯一一个被翻转了 x 次的区域，据此可知一条被选中的弦恰好对应一个只被翻转了 1 次的区域。所以总贡献就是 n\times 2^{n-1}，意思就是对于每条弦，只要它被选了，就会产生 1 的贡献。

考虑被翻转了超过 3 次怎么做：显然我们需要选择恰好 x 条两两相交的弦，这很困难。但是我们可以考虑选择两条相交的弦 i<j，然后再考虑在 i 到 j 中间的弦中进行选择。因为 i 与 j 相交，所以你在中间怎么随便选，选出来的也一定是两两相交的。假设 i 到 j 中间一共有 m 条弦，那么当 m=0 时，选出奇数条弦的方案和是 0；当 m>0 时，方案和是 2^{m-1}（经典 trick，可以理解为先选 m-1 了，剩下一个如果前面已经选了奇数个就不会选，否则选）。i\sim j 外面随便选，方案数是 2^{n-m-2}，所以总方案数是 2^{m-1}\times 2^{n-m-2}=2^{n-3}，注意最后的式子和 m 无关。

所以做法就很明了了，记相交但是不连续（因为我们要使得 m>0）的两条弦的个数是 w 个，那么答案就是：

n2^{n-1}+w2^{n-3}

注意特判 n<3。时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 250010, P = 998244353;
inline int add(int x, int y) { if (x + y >= P) return x + y - P; return x + y; }
inline int sub(int x, int y) { if (x - y < 0) return x - y + P; return x - y; }
inline int mul(int x, int y) { return 1LL * x * y % P; }
inline void Add(int& x, int y) { x = add(x, y); }
inline void Sub(int& x, int y) { x = sub(x, y); }
inline void Mul(int& x, int y) { x = mul(x, y); }
inline int qpow(int x, int y = P - 2) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
int l, k, n, a[2 * N], ans;
int main() {
    scanf("%d %d %d", &l, &k, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[n + i] = a[i] + l;
    ans = mul(n, qpow(2, n - 1));
    int w = 0;
    for (int i = n + 1, j = 0; i <= 2 * n; i++) {
        if (j <= i - n) j = i - n + 1;
        while (a[j] + k <= a[i]) j++;
        int cnt = i - j;
        if (cnt >= 1) Add(w, cnt - 1);
    }
    if (n >= 3) Add(ans, mul(w, qpow(2, n - 3)));
    cout << ans << endl;
}