dede 网站搬家/新浪nba最新消息

传送门:bzoj3811

题解

法1(线性基):
根据$k\le 5$分类讨论并拆位：

• $k=1$时：对于某一位，若数列中所有数该位不全为0，则出现奇数个1的概率必然为$\frac{1}{2}$(假设有$m$个数该位为$1$，$2^m$种方案中显然大小一半为奇一半为偶)。答案即为所有数异或和/2。
• $k=2$时，设第$i$位异或和为1的概率为$w_i$，$(\sum w_i{2}^i{)}^2={\sum }_i{\sum }_j(w_i{w}_j{2}^{i+j})$，不可统计的平方的期望转成了指定两位乘积的期望(同时为1的概率)。若数列中所有数第$i,j$位都不全为0，则概率为$\frac{1}{2}\times \frac{1}{2}=\frac{1}{4}$（*注意特判，对于所有数它们的第$i,j$位都相同时，概率为$\frac{1}{2}$）
• $k\ge 3$时，$a_i\le 2^{21}$，暴力线性基统计即可，注意中间过程答案可能溢出$2^{63}$，所以设线性基有效位数为$m$，记录$a=\lfloor \frac{x^k}{2^m}\rfloor ,b=x^{k}mod{2}^m$，而$x^{k+1}=a\times x+\lfloor \frac{b\times x}{2^m}\rfloor +(b\times xmod{2}^m)$，即$a^{\prime }=a+\lfloor \frac{b\times x}{2^m}\rfloor ,b^{\prime }=b\times xmod{2}^m$。

法2(高斯消元)：

其实就是法1中$k=2$的拓展。

因为答案$\le 2^{63}$，所以
$k=1\to a_i\le 2^{63}$
$k=2\to a_i\le 2^{32}$
$k=3\to a_i\le 2^{21}$
$k=4\to a_i\le 2^{16}$
$k=5\to a_i\le 2^{13}$

假设$a_i\le 2^m$，则答案$(\sum w_i{2}^i{)}^k={\sum }_{x_1}...{\sum }_{x_k}(w_{x_1}...w_{x_k}{2}^{\sum x_i})$

暴力$O(m^k)$枚举$k$个指定的位，剩下的问题就是求解{x1,...,xk}\{x_1,...,x_k\}{x1​,...,xk​}均为1的概率，可以列出$k$个$n$元一次异或方程组，高斯消元求解。概率即为${\frac{1}{2}}^{非零行数}$。

$复杂度O(能过)$

代码

注意开$\text{unsigned long long}$

法1

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e5+10;int n,K;
ll a[N],b[65],ans,res;char cp;
template<class T>inline void rd(T &x)
{cp=getchar();x=0;for(;!isdigit(cp);cp=getchar());for(;isdigit(cp);cp=getchar()) x=x*10+(cp^48);
}inline void sol1()
{for(int i=1;i<=n;++i) ans|=a[i];printf("%llu",ans>>1);puts((ans&1)?".5":"");
}inline void sol2()
{int i,j,k;ll sum=0;for(i=1;i<=n;++i) sum|=a[i];for(i=0;i<33;++i) if((sum>>i)&1)for(j=0;j<33;++j) if((sum>>j)&1){for(k=1;k<=n && ((a[k]>>i)&1)==((a[k]>>j)&1);++k);if((!i)&&(!j)) {res++;continue;}if(k>n) ans+=1uLL<<(i+j-1);else i+j<2?res++:ans+=1uLL<<(i+j-2);}ans+=res>>1;printf("%llu",ans);puts((res&1)?".5":"");
}int cnt,S;
ll g[65];inline void sol3()
{int i,j;ll v,x,y;for(i=1;i<=n;++i)for(v=a[i],j=21;(~j)&&v;--j) if((v>>j)&1){if(b[j]) v^=b[j];else{b[j]=v;g[cnt++]=v;break;}}S=(1<<cnt)-1;for(i=0;i<=S;++i){for(v=0LL,j=0;j<cnt;++j) if((i>>j)&1) v^=g[j];for(x=0,y=1,j=0;j<K;++j){x*=v;y*=v;x+=(y>>cnt);y&=S;}ans+=x;res+=y;ans+=(res>>cnt);res&=S;}printf("%llu",ans);puts(res?".5":"");
}int main(){rd(n);rd(K);for(int i=1;i<=n;++i) rd(a[i]);if(K==1) sol1();else if(K==2) sol2();else sol3();return 0; 
}