Description

link

从一个序列里面选择一些数异或起来，求所有异或方案的答案的 \(k\) 次方的期望值

\(n \le 100000,1\le k \le 5\)

Solution

这个 \(k\) 次方很玄学，那么从这里入手（看了这一句题解之后大骂自己与\(sb\)无异十遍）

---

我们发现题目中说的 \(ans \le 2^{63}\)

所以对于 \(k \ge 3\) 的，线性基的大小不会超过 \(63/3=21\)

外加一个结论，原序列能异或出来的数，每个会重复 \(2^{n-siz}\) 次，所以我们期望就是 \(\frac {sum}{2^k}\)（这里一开始想到了，但是那个\(2^63\) 给我整怵了）

这 \(0/1\ dfs\) 算就好了……

---

发现 \(k\) 等于 \(1\) 的时候，对于每一位考虑（这可还行……）

如果至少有一个数的当前位是 \(1\) 的，那么有一半的可能性为 \(0\)

如果不止一个 \(1\) 的情况下显而易见地发现这概率还是一半（手玩几个）

---

最后是 \(k\) 是 \(2\) 的期望

因为是个平方，所以我们在乘的时候要考虑两个带 \(1\) 的位置

同时因为这是个期望，所以要看所有数的对应位置的值

讨论一下就行了

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	#define ul unsigned long long
	inline ul read()
	{
		ul res=0; char k;
		while(!isdigit(k=getchar()));
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res;
	}
	int p[30],s,siz,n,m,pos,las,cnt;
	ul ans,a[100010];
	inline void insert(int x)
	{
		for(int i=siz;i>=0;--i)
		{
			if(!(x>>i)) continue;
			if(!p[i]){p[i]=x; pos++; break;}
			else x^=p[i]; 
		} return ;
	}
	inline void solve()
	{
		ul res=0;
		for(int i=1;i<=n;++i) a[i]=read();
    	for(int i=0;i<=32;i++)
    	{
    		for(int j=0;j<=32;j++)
    		{
		 		int fg1=0,fg2=0,fg3=0;
		 		for(int k=1;k<=n;k++)
		 		{
		  		   	if(a[k]>>i&1)fg1=1;
		 		   	if(a[k]>>j&1)fg2=1;
		    	    if((a[k]>>i&1)!=(a[k]>>j&1))fg3=1;
		     	   	if(fg1&&fg2&&fg3)break;
		    	}
		    	if(!fg1||!fg2)continue;
		    	if(i+j-fg3-1<0)res++;
		    	else ans+=1ull<<(i+j-fg3-1);
    		}
    	}
    	ans+=res>>1; res&=1; 
   		printf("%llu",ans);
    	if(res)printf(".5\n");
    	else puts("");
    	return ;
	}
	signed main()
	{
		n=read(); m=read();
		if(m==1)
		{
			ul res=0;
			for(int i=1;i<=n;++i) res|=read();
			if(res%2==0) printf("%llu\n",res/2);
			else printf("%llu.5\n",res/2);
			return 0; 	
		}
		if(m==2) solve();
		if(m>=3)
		{
			for(int i=1;i<=n;++i) a[i]=read();
			if(m==3) siz=22; else if(m==4) siz=15; else siz=12;
			for(int i=1;i<=n;++i) insert(a[i]);
			for(int i=0;i<=siz;++i) if(p[i]) a[cnt++]=p[i]; s=1<<pos;
			for(int i=0;i<s;++i)
			{
				int x=0;
				for(int j=0;j<cnt;++j) 
				{
					if((i>>j)&1) x^=a[j]; 
				} 
				int r1=0,r2=1;
				for(int j=1;j<=m;++j)
				{
					r2*=x; r1*=x; r1+=r2>>pos; r2&=s-1;
				}
				ans+=r1; las+=r2; ans+=las>>pos; las&=s-1; 
			} 
			printf("%lld",ans); if(las) puts(".5"); else puts("");
		}
		return 0;
	}
}
signed main(){return yspm::main();}

``