BZOJ3687 简单题

题意

给出四个问题:
1.子集的异或和的算术和
2.子集的异或和的异或和
3.子集的算术和的算术和
4.子集的算术和的异或和
请解决四个问题

题解

虽然只要解决第四个,但还是随便打了打前面的问题
前三个问题之和暴力拍了一下没错,不保证实际正确性

问题1

要求异或和的算数和
显然可以将每一位分别考虑
枚举当前位 $j$ 设 $f[i][0/1]$ 表示前 $i$ 个数字的子集,异或起来后第 $j$ 位为 $0/1$ 的方案数
转移:
不选当前数
$$ f[i][k]=f[i][k]+f[i-1][k] $$
选当前数,设当前数在第 $j$ 位上的数字为 $x(x\in {0,1})$
$$ f[i][0] = f[i][0]+f[i-1][x] $$
$$ f[i][1] = f[i][1]+f[i-1][x\oplus 1] $$
转移之后对每一位统计答案

问题2

要求子集的异或和的异或和
当 $n=1$ 时答案为 $a[1]$
否则答案为 $0$
正确性显然

问题3

要求子集的算术和的算术和
考虑某个数会出现在多少个子集中,也就是会有多少次贡献
实际上相当于选出这个数然后把剩下 $n-1$ 个数生成子集,共 $2^{n-1}$ 种方案
所以答案为
$$ \sum_{i=1}^{n} a[i]\times 2^{n-1} $$

问题4

要求子集的算术和的异或和
发现元素的和十分少,且只需要求子集和的异或和,对于如果子集和为 $x$ ,那么只需要知道子集和为 $x$ 的子集个数是奇数还是偶数
那么不妨设 $f[j][i]$ 表示前j个元素,和为 $i$ 的子集个数是奇数还是偶数
如果是奇数就是 $1$ ,偶数就是 $0$
那么如果当前第 $j+1$ 个数为 $x$ ,那么 $f[j+1][i]=f[j][i]\oplus f[j][i-x]$
如果我们将 $f[j]$ 数组看做一个长度为 $n$ 的二进制串,实际上就是 $f[j+1]=f[j]\oplus (f[j]<<x)$
我们可以用 $bitset$ 存下这个二进制串,可以 $STL$ 也可以自己写

代码

#define MAX_N 2007
#define MOD 998244353

int N, T;
ll a[MAX_N];
ll f[MAX_N][2], res;
std::bitset<2000007> g;

inline ll quick_pow (ll x, ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
        p >>= 1;
    }
    return ans % MOD;
}

inline void solve_front () {
    read(T);
    read(N);
    for (int i = 1; i <= N; ++i)
        read(a[i]);
    if (T == 1) {
        for (int i = 0; i < 22; ++i) {
            memset(f, 0, sizeof(f));
            f[0][0] = 1;
            for (int j = 1; j <= N; ++j) {
                (f[j][0] += f[j - 1][0]) %= MOD;
                (f[j][1] += f[j - 1][1]) %= MOD;
                (f[j][0] += f[j - 1][a[j] >> i & 1]) %= MOD;
                (f[j][1] += f[j - 1][(a[j] >> i & 1) ^ 1]) %= MOD;
            }
            (res += (1 << i) * f[N][1] % MOD) %= MOD;
        }
        printf("%lld\n", res);
    } else if (T == 2) {
        if (N > 1) puts("0");
        else printf("%lld\n", a[1]);
    } else if (T == 3) {
        for (int i = 1; i <= N; ++i)
            (res += a[i] * quick_pow(2LL, (ll)(N - 1)) % MOD) %= MOD;
        printf("%lld\n", res);
    }
}

inline void solve_real () {
    g = 1;
    int x;
    for (int i = 1; i <= N; ++i) {
        scanf("%d", &x);
        g = g ^ (g << x);
    }
    for (int i = 0; i <= 2000000; ++i)
        res ^= g[i] * i;
    printf("%lld\n", res);
}

int main () {
    read(N);
    if (N == 1234567)
        solve_front();
    else solve_real();
    return 0;
}

引用资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注