【题解】Hihocoder 1526 Sequence Value

请注意,本文编写于 98 天前,最后修改于 98 天前,其中某些信息可能已经过时。

Problem

定义一个序列 $a[1\cdots n]$ 的价值 $val(a)$ 为 $\sum_{i=1}^{n}[sum[i]>sum[i-1]]$ ,其中 $sum[n]=\oplus_{i=1}^{n}a[i]$

求给定序列所有子序列的价值和

Thought

考场跑偏系列

假设 $a[i]$ 有贡献,那么需要计算 $a[1]-a[i-1]$ 中所有子序列(包括空串)有多少个的异或和 $s$ 使得 $s\oplus a[i]>s$ ,然后后面的就任选呗

这是正常的思路

而某二货的思路是:
对于一个子序列,其贡献为其前缀异或和序列的 $01$ 个数,然后用了一大堆东西维护, $GG$

不扯远了

考虑如何求出前面有多少个子序列满足 $s \oplus a[i]>s$

如果前面的数最高位比 $a[i]$ 的最高位要高,那么更高位其实并没有什么卵用,所以压到和 $a[i]$ 一样高(然后 $a[i]$ 就能凭借丰富的经验打败你)

可以使得 $a[i]$ 做出贡献的 $s$ 在压到和 $a[i]$ 同位后满足最高位为 $0$

那么考虑每一位为 $0$ 的子序列有多少个,这个拆成 $31$ 次分开做就好了
时间复杂度 $O(31n)$

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int mod = 998244353;
int n, a[N];
int bin[31];
int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    bin[0] = 1;
    for(int i = 1; i < 31; ++ i)
        bin[i] = bin[i - 1] << 1;
    n = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    int ans = 0;
    for(int w = 30; w >= 0; -- w) {
        int One = 0, Zero = 0;
        for(int i = 1; i <= n; ++ i) {
            if(a[i] & bin[w]) {
                if(a[i] - bin[w] < bin[w]) {
                    ans += 1ll * (Zero + 1) * qpow(2, n - i) % mod;
                    ans %= mod;
                }
                Zero = (One + Zero) % mod;
                One = (Zero + 1) % mod;
            }
            else {
                One = (One * 2) % mod;
                Zero = (Zero * 2 + 1) % mod;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}
Comments

添加新评论