组队训练赛（三）

组队训练赛（三）¶

题目1¶

题目链接¶

题目描述¶

样例输入¶

样例输出¶

15
168

题解¶

把 N 个物品理解为向量，先想二维的情况

F[A][B] = v[A][B]

F[A][B] += F[0][B] + F[A][0]

推广到 N 维：

F[A][B][C][D][E]... = v[A][B][C][D][E]...

F[A][B][C][D][E]... += v[A][0][0][0][0]... + ...

写成容斥，在维度上是不好扩展的。而写成空间向量的理解，是很好扩展的

加上二进制位运算

参考链接：

https://blog.nowcoder.net/n/fba9bdd58cda4937a10bbd293bd3a7ec

https://blog.csdn.net/eternity19/article/details/119735293

代码¶

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[50] = {0};
ll ans[1050000] = {0};
ll sum1[1050000] = {0};
ll sum2[1050000] = {0};
int main()
{
    //     freopen("in.txt", "r", stdin);
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    for (ll i = 0; i < (1 << n); i++)
    {
        for (ll j = 0; j < n; j++)
            if ((i >> j) & 1)
                ans[i] ^= a[j];
        sum1[i] = ans[i];
        sum2[i] = ans[i];
    }
    for (ll j = 0; j < n; j++) \\依次考虑放置每一个物品
    {
        for (ll i = 0; i < (1 << n); i++)
        {
            if ((i >> j) & 1)
                sum1[i] += sum1[i ^ (1 << j)];
            else
                sum2[i] += sum2[i ^ (1 << j)];
        }
    }
    for (ll i = 1; i <= m; i++)
    {
        ll k, m, p = 0;
        scanf("%lld", &k);
        for (ll j = 1; j <= k; j++)
        {
            scanf("%lld", &m);
            m--;
            p += (1 << m);
        }
        printf("%lld %lld\n", sum1[p], sum2[p]);
    }
    return 0;
}