Description
魔法之龙玛里苟斯最近在为加基森拍卖师的削弱而感到伤心，于是他想了一道数学题。
S 是一个可重集合，S={a1,a2,…,an}。
等概率随机取 S 的一个子集 A={ai1,…,aim}。
计算出 A 中所有元素异或 x, 求 xk 的期望。
Input
第一行两个正整数 n, k。
以下 n 行每行一个整数，表示 ai。
Output
如果结果是整数，直接输出。如果结果是小数（显然这个小数是有限的），输出精确值（末尾不加多余的 0）。
Sample Input
4 2
0
1
2
3
0
1
2
3
Sample Output
3.5
HINT
限制与约定
1≤n≤100000，1≤k≤5，ai≥0。最终答案小于 2^63 。k=1,2,3,4,5 各自占用 20% 的数据
Source
Solution
被学长安利去做这道题。。。线性基。
考虑一个性质：如果把集合内的一个数异或上另一个数，则这个集合的子集的异或和的集合不变。
什么叫做子集的异或和的集合？就是你从一个集合中选出一个子集，这个有2^n种选法，把选出来的数异或起来，然后这些异或起来的数组成的集合。
考虑证明：
假如我们一开始的集合是{a,b,...}，我们把b异或上a，得到{a,a^b,...}。
然后原来和b有关但与a无关的子集的异或和，我们可以用a异或上a^b来代替；
原来和a和b都有关的子集的异或和，我们现在可以直接用a^b来代替。
其他的集合因为没有变，所以还是不变的。
那么总共产生的集合还是没有变。
既然我们有这么一个操作，那么我们就可以按位高斯消元了。我们把原集合高斯消元后得到的集合称作线性基（听别人说好像也叫秩？我对线代一无所知，所以不是很懂）。
可以证明线性基的个数是log权值的。
这题就是把式子展开完dfs一下。。。（你要是愿意每个子任务写k个for也是可以的）
Code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> #ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif #ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout)
#endif #define R register
#define getc() (_S == _T && (_T = (_S = _B) + fread(_B, 1, 1 << 15, stdin), _S == _T) ? EOF : *_S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
#define cabs(_x) ((_x) < 0 ? (- (_x)) : (_x))
char _B[ << ], *_S = _B, *_T = _B;
typedef unsigned long long ull;
inline ull F()
{
R char ch; R ull cnt = ; R bool minus = ;
while (ch = getc(), (ch < '' || ch > '') && ch != '-') ;
ch == '-' ? minus = : cnt = ch - '';
while (ch = getc(), ch >= '' && ch <= '') cnt = cnt * + ch - '';
return minus ? -cnt : cnt;
}
typedef long long ll;
ull b[], c[];
int top, m, sum, n, k, tmp, sn[], maxlen;
ll ans;
bool flag;
void dfs(R int step, R ull state)
{
if (!step)
{
R int cnt = ;
memset(c, , (m + ) << );
for (R int i = ; i <= m; ++i)
{
R ull x = b[i] & state;
for (; x; )
{
tmp = __builtin_ctzll(x);
if (!c[tmp])
{
c[tmp] = x;
break;
}
x ^= c[tmp];
}
}
for (R int i = m; i >= ; --i)
if (c[i])
for (R int j = i - ; j >= ; --j)
if (c[j] & (1ull << i))
c[j] ^= c[i];
R ull summ = ;
for (R int i = ; i <= m; ++i) if (c[i]) ++cnt, summ ^= c[i];
if (summ != state) return ;
// printf("%d %d\n", cnt, sum );
if (sum < cnt)
{
++sn[cnt - sum];
cmax(maxlen, cnt - sum);
}
else ans += 1ull << (sum - cnt);
return ;
}
for (R int i = ; i <= m; ++i)
{
sum += i;
dfs(step - , state | (1ull << i));
sum -= i;
}
}
int main()
{
// setfile();
n = F(), k = F();
for (R int i = ; i <= n; ++i)
{
R ull x = F();
cmax(m, - __builtin_clzll(x));
for (; x; )
{
tmp = __builtin_ctzll(x);
if (!b[tmp])
{
b[tmp] = x;
break;
}
x ^= b[tmp];
}
}
for (R int i = m; i >= ; --i)
if (b[i])
for (R int j = i - ; j >= ; --j)
if (b[j] & (1ull << i))
b[j] ^= b[i];
// for (R int i = 0; i <= m; ++i) printf("%llu ", b[i] );
dfs(k, );
for (R int i = maxlen; i; --i)
{
sn[i - ] += sn[i] >> ;
sn[i] %= ;
}
ans += sn[];
printf("%llu", ans );
sn[] ? puts(".5") : ;
return ;
}