TC SRM628 DIV1
ProjectEuler 559

BZOJ 3811: 玛里苟斯

YYY posted @ 2016年5月12日 21:06 in 算法竞赛 with tags 高斯消元 线性基 , 1231 阅读
_THIS_IS_START_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,那么显然这两位就是相互独立的,否则是不相互独立的
-------------------------------------------------------------
 

 

_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter