【清华集训 2014】玛里苟斯（组合计数 + 线性基）

　

玛里苟斯

题目链接：【清华集训 2014】玛里苟斯

推荐博客：【BZOJ 3811】玛里苟斯：线性基（详细证明）

首先想到将k" role="presentation" style="position: relative;">k$k$分类讨论。

k=1" role="presentation" style="position: relative;">k=1$k=1$时，我们考虑每一位的贡献。若有至少一个数第i" role="presentation" style="position: relative;">i$i$位为1" role="presentation" style="position: relative;">1$1$，则对答案的贡献为valuei2" role="presentation" style="position: relative;">valuei2$\frac{valu{e}_i}{2}$。

k=2" role="presentation" style="position: relative;">k=2$k=2$时，发现每个异或和的平方为∑i∑j2i+jbitibitj" role="presentation" style="position: relative;">∑i∑j2i+jbitibitj$\sum _i\sum _j{2}^{i+j}bi{t}_{i}bi{t}_j$。那么考虑第i" role="presentation" style="position: relative;">i$i$位和第j" role="presentation" style="position: relative;">j$j$位的积的期望值。如果所有的数中，第i" role="presentation" style="position: relative;">i$i$位和第j" role="presentation" style="position: relative;">j$j$位均相等且非全零，那么参考k=1" role="presentation" style="position: relative;">k=1$k=1$的情况，期望为12" role="presentation" style="position: relative;">12$\frac{1}{2}$；否则，第i" role="presentation" style="position: relative;">i$i$位为1" role="presentation" style="position: relative;">1$1$的概率为12" role="presentation" style="position: relative;">12$\frac{1}{2}$，第j" role="presentation" style="position: relative;">j$j$位为1" role="presentation" style="position: relative;">1$1$的概率为12" role="presentation" style="position: relative;">12$\frac{1}{2}$，i×j" role="presentation" style="position: relative;">i×j$i\times j$为1" role="presentation" style="position: relative;">1$1$的概率为14" role="presentation" style="position: relative;">14$\frac{1}{4}$。

k≥3" role="presentation" style="position: relative;">k≥3$k\ge 3$时， 由于答案不超过263" role="presentation" style="position: relative;">263$2^{63}$，所以每个数不超过221" role="presentation" style="position: relative;">221$2^{21}$，所以线性基个数不超过21" role="presentation" style="position: relative;">21$21$，则可以暴力枚举异或和来计算答案了。注意精度问题。

我怀疑我学了假的线性基模版···

#include <cstdio>
#include <iOStream>
const int maxn = 100005;
typedef unsigned long long ull;
int n, m, k;
ull a[maxn], base[maxn], b[maxn];
void solve1() {
    ull ans = 0;
    for (int i = 1; i <= n; i++) {
        ans |= a[i];
    }
    printf("%llu", ans >> 1);
    if (ans & 1) {
        printf(".5");
    }
    putchar('\n');
}
void solve2() {
    ull ans = 0, res = 0;
    for (int i = 32; i >= 0; i--) {
        for (int j = 32; j >= 0; j--) {
            bool flag0 = 0, flag1 = 0, flag = 0;
            for (int k = 1; k <= n; k++) {
                flag0 |= a[k] >> i & 1;
                flag1 |= a[k] >> j & 1;
                flag |= (a[k] >> i & 1) != (a[k] >> j & 1);
            }
            if (!flag0 || !flag1) {
                continue;
            }
            if (i + j - flag - 1 < 0) {
                res++;
            } else {
                ans += 1ull << (i + j - flag - 1);
            }
        }
    }
    ans += res >> 1;
    printf("%llu", ans);
    if (res & 1) {
        printf(".5");
    }
    putchar('\n');
}
void solve3() {
    ull ans = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 22; j >= 0; j--) {
            if (a[i] >> j & 1) {
                if (base[j]) {
                    a[i] ^= base[j];
                } else {
                    base[j] = a[i];
                    b[++m] = a[i];
                    break;
                }
            }
        }
    }
    for (int i = 0; i < 1 << m; i++) {
        ull val = 0;
        for (int j = 1; j <= m; j++) {
            if (i >> (m - j) & 1) {
                val ^= b[j];
            }
        }
        ull a = 0, b = 1;
        for (int j = 1; j <= k; j++) {
            a *= val, b *= val;
            a += b >> m, b &= (1 << m) - 1;
        }
        ans += a, res += b;
        ans += res >> m, res &= (1 << m) - 1;
    }
    printf("%llu", ans);
    if (res) {
        printf(".5");
    }
    putchar('\n');
}
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%llu", a + i);
    }
    if (k == 1) {
        solve1();
    } else if (k == 2) {
        solve2();
    } else {
        solve3();
    }
    return 0;
}

相关阅读

2014年上海最低工资标准

最低工资是指劳动者在法定工作时间提供了正常劳动的前提下，其雇主或用人单位支付的最低金额的劳动报酬。最低工资标准一般由一个国

（转）【电子书分享】《MATLAB 7.0 基础教程》-清华大学出

直接给链接： 《MATLAB 7.0 基础教程》-清华大学出版社-孙祥等编著 1.pdf: https://u8266128.pipipan.com/fs/8266128-301596145—

2014淘宝双十一具体玩法，你知道多少？

一年一度的双十一又来了，与往年不一样的是，今年的双十一是阿里全集团的双十一，也是淘宝网今年后续最气势宏大的两场活动之一。双十一

2014年互联网大事件回顾（完整版）

脆弱的DNS2014年1月21日下午15：20开始，国内大部分网站，包括大型门户新浪、百度等以及导航、视频无法加载，账号无法登陆，DNS域名解析系

2014年针对单品营销我们还有什么办法

回首过去一年，有人盆满钵盈，有人怨声载道，但是无论结果怎样，大家都有一个共同的心声，相信电脑前的你也一样，就是——淘宝越来越难做了。