xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 AT5799 【[AGC043B] 123 Triangle】

首先进行一次绝对值差分,让序列中的数都在 $0 \sim 2$ 中,显然无论什么情况后面的每个数只可能为 $0 \sim 2$。

如果此时的序列中存在 $1$,则意味着答案只可能是 $0$ 或 $1$;如果不存在 $1$,则答案只可能是 $0$ 或 $2$。

对于不存在 $1$ 的情况,我们可以将每个数都 $\div 2$,最后再将答案 $\times 2$,这显然是等价的。

于是现在的答案都只可能是 $0$ 或 $1$ 了,于是显然我们只用在模 $2$ 的情况下讨论。

考虑一次绝对值差分在模 $2$ 意义下的影响,可以发现等价于 $\operatorname{xor}$。

现在问题变为,给定一个 $0/1$ 序列,每次将相邻两个数 $\operatorname{xor}$,求最后剩下的数。

那么考虑每个数会被异或几次即可,设序列长度为 $n$,则位置 $i$ 上的数会被异或 $\binom {n-1}{i-1}$ 次。

这时候我们还要求出模 $2$ 意义下的组合数,一个简单的方法是计算每个阶乘的分解中 $2$ 的次数,将计算组合数时的除法改为做减法。则对于一个组合数,最后如果剩下的 $2$ 的次数为 $0$,则说明 $\bmod 2 = 1$,否则 $\bmod 2 = 0$。

对于阶乘的分解,可以先对每个数简单地求出分解中 $2$ 的次数,然后做前缀和即可。

时间复杂度 $\mathcal O(n)$。

const int N = 1e6 + 7;
int n, a[N], c[N];
char s[N];

int main() {
    rd(n), rds(s, n), --n;
    for (int i = 1; i <= n; i++) a[i] = abs(s[i] - s[i+1]);
    bool ok = 0;
    for (int i = 1; i <= n; i++)
        if (a[i] == 1) ok = 1;
    if (!ok) for (int i = 1; i <= n; i++) a[i] >>= 1;
    for (int i = 1; i <= n; i++) {
        int x = i;
        while (!(x & 1)) ++c[i], x >>= 1;
        c[i] += c[i-1];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans ^= c[n-1] - c[i-1] - c[n-i] ? 0 : (a[i] & 1);
    if (!ok) ans <<= 1;
    print(ans);
    return 0;
}

2020-03-22 16:10:15 in 题解