【题解】玛里苟斯 线性基+乱搞 Uoj #36 ——quhengyi11

传送门

吐槽

$k\leq 5$(法术伤害+5)

题解

因为答案保证了范围，考虑线性基

当 $k\geq 3$的时候，显然值域范围 $\leq 2^{22}$因此我们可以直接把所有数插入线性基，然后枚举算即可 (tip: 易知每个数的出现次数相同)

当 $k=1$的时候，也容易想到按二进制位讨论贡献，当讨论到第 $i$位的时候，如果这个位上全都是 $0$显然贡献都是 $0$了，否则设 $1$的个数为 $a$个，则 $0$的个数为 $n-a$个，显然对答案有 $2^i$贡献的只有 $2^{n-a}\sum C_a^i \times[i\&1] $个，也就是 $2^{n-1}$个，所以它的贡献就是 $\frac 1 2$，所以只需要看看这一位有没有 $1$，有的话贡献就是 $\frac 1 2$否则为 $0$

然后你获得了 $80$分的好成绩

当 $k=2$的时候就有点麻烦，因为线性基值域是 $[0,2^{32})$的所以我们还是只能按位考虑贡献，考虑枚举第 $i$位和第 $j$位，考虑它们对 $2^{i+j}$的贡献，记 $a_{i,j}$表示第 $i$个数二进制位下的第 $j$位，显然只有 $a_{x,i}$，$a_{y,j}$同时为 $1$的时候才会造成贡献，如果 $\forall x\;a_{x,i}$都为 $0$，那么显然不会造成贡献，$a_{y,j}$同理，如果 $\forall \; a_{x,i}=a_{y,i}$，则它们相当于只有一位，贡献是 $\frac 1 2$，其它情况贡献都是 $\frac 1 4$的，用类似 $k=1$的证明消掉两个组合数即可

这个 $k=2$的复杂度有点卡，不过一般不会超时

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll unsigned long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10086
#define lowbit(x) (x & -x)
#define N 100005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
#define ld long double
inline void read (int &x)
{
    x = 0;
    Re char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
int n, base, cnt, tot, k;
ll b[N];
inline void ins (int x)
{
    fd (j, base, 0)
        if (x >> j & 1)
        {
            if (b[j]) x ^= b[j];
            else
            {
                ++cnt;
                b[j] = x;
                fd (k, j - 1, 0) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];
                fo (k, j + 1, n) if (b[k] >> j & 1) b[k] ^= b[j];
                break;
            }
        }
}
ll a[N];
ld sum = 0, tmp;
inline void work1 ()
{
    ll ans = 0;
    fo (i, 1, n) ans |= a[i];
    printf("%lld", ans >> 1);
    if (ans & 1) printf(".5");
}
inline void work2 ()
{
    base = 31;
    ll ans = 0;
    ll res = 0;
    fo (i, 0, base)
        fo (j, 0, base)
        {
            bool fl = 0;
            fo (k, 1, n) if (a[k] >> i & 1) fl = 1;
            if (!fl) continue;
            fl = 0;
            fo (k, 1, n) if (a[k] >> j & 1) fl = 1;
            if (!fl) continue;
            fl = 0;
            fo (k, 1, n) if ((a[k] >> i & 1) ^ (a[k] >> j & 1)) { fl = 1; break; }
            if (i + j - fl - 1 < 0) ++res; else 
            if (!fl)
                ans += 1ll << i + j - 1;
            else
                ans += 1ll << i + j - 2;
        }
    ans += res >> 1; res &= 1;
    printf("%lld", ans);
    if (res) printf(".5");
}
inline void work3 ()
{
    base = 22;
    fo (i, 1, n) ins(a[i]);
    fo (i, 0, base) if (b[i]) a[++tot] = b[i];
    int up = (1 << cnt) - 1;
    fo (i, 0, up)
    {
        ll now = 0;
        fo (j, 1, cnt)
            if (i >> j - 1 & 1)
                now ^= a[j];
        tmp = now;
        fo (i, 2, k) tmp = tmp * now;
        sum = sum + tmp;
    }
    printf("%llu", (ll) (sum / (up + 1)));
    if ( (ld((ll)(sum / (up + 1)))) * (up + 1) != sum) printf(".5");
}
int main ()
{
    read(n); read(k); fo (i, 1, n) scanf("%llu", &a[i]);
    if (k == 1) work1(); else
    if (k == 2) work2(); else
        work3();
    return 0;
}