BZOJ 3811: 玛里苟斯
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
-------------------------------------------------------------
对线性基还是不熟啊...
-------------------------------------------------------------
首先随便算一下发现每一位只要有可能出现1，出现1的概率一定是50%，从而所有能出现的数出现的概率都是一样的（但并不是所有数都能出现，因为有些位的1是相关的）
然后因为答案<=2^63，所以当k>=3的时候就有x<=2^21
而如果能枚举所有可能出现的答案，答案就好求了
因为x<=2^21，S中所有元素一定<=2^21,从而S的线性基大小不会超过21
因此把S的线性基求出来，2^k枚举一下看能出现哪些数就行了
现在考虑k<3的情况
k=1很简单，所有能出现1的位乘以50%加起来就是了
k=2时，答案可以看成是$(10^{a1}+10^{a1} ..10^{ak})^{2}$，因此可以枚举两位i，j，考虑$10^i$和$10^j$产生贡献的概率（而贡献的大小显然是$10^{2*(i+j)}$），显然如果这两位相互独立，那么同时出现的概率就是25%,而如果不相互独立，同时出现的概率就是50%，而只要有一个数是这两位中只有一位为1，那么显然这两位就是相互独立的，否则是不相互独立的
-------------------------------------------------------------
评论 (0)
