CF2006C Eri and Expanded Sets

TernaryTree · 2024-08-31 21:19:43 · 题解

出题人题解。考虑一个集合 S 进行“扩展”操作后，得到的 S' 会是什么样子。

• 显然。
• 反证，若不是等差数列，设存在三个相邻的数，在数轴上的相邻距离为 $d_1\neq d_2$。若 $d_1,d_2$ 为偶数显然不是最终状态；否则都为奇数，有 $d_1+d_2$ 是偶数，则可以生成新的数。
• 设公差为 $d$，设最小值为 $l$。有 $\forall i\in S, i=l+kd$。容易发现 $d$ 一定要是所有差分值的因数，即所有差分 $\gcd$ 的因数。同时发现构造出中间过程公差恰好为 $\gcd$ 是容易的，再往后只有可能将公差缩小一半。
• 显然，若为偶数可以继续拓展。

• 设 S 相邻两项差分值的 \gcd 是 g，则 S' 的公差是 \dfrac{g}{\operatorname{lowbit}(g)}。

  由上面两条结论不难得到。

于是转化为了这样一个问题：求有多少区间的 \gcd 形如 2^k 或 0。对于固定的左端点，区间 \gcd 形如 2^k 的 r 是一段后缀；而形如 0 的是一段 l 开头后缀的前缀。

因为端点有单调性，貌似可以使用 baka's trick 做到比较好看的复杂度，但是我比较蠢，写了个二分 ST 表，两只 \log，也可以通过。

int query(int l, int r) {
    int d = __lg(r - l + 1);
    return __gcd(st[d][l], st[d][r - (1 << d) + 1]);
} 

bool check(int x) {
    return x && (x & -x) == x;
}

void fake_main() {
    n = read(), ans = n;
    rep(i, 1, n) a[i] = read();
    rep(i, 1, n - 1) st[0][i] = b[i] = abs(a[i] - a[i + 1]);
    rep(d, 1, maxd - 1) rep(i, 1, n - (1 << d)) st[d][i] = __gcd(st[d - 1][i], st[d - 1][i + (1 << d - 1)]);
    rep(i, 1, n - 1) {
        if (check(query(i, n - 1))) {
            int l = i, r = n - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (check(query(i, mid))) r = mid;
                else l = mid + 1;
            }
            ans += n - l;
        }
        if (!b[i]) {
            int l = i, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1; 
                if (!query(i, mid)) l = mid;
                else r = mid - 1;
            }
            ans += l - i + 1;
        }
    }
    write(ans), pc('\n'); 
}