bzoj3811:玛里苟斯(DP+线性基)

Author Avatar
Sakits 4月 21, 2018

题解

  清华集训的神题…题解看得我一愣一愣的,全都想不到…
  kk比较小,可以分类讨论。
  k=1k=1时,若某一位上有11,那么显然答案上这一位是11的概率就是0.50.5,否则为00
  k=2k=2时需要推推式子。设aia_i2n2^n种方案异或出来的数,则答案为:

i=12nai22n\frac{\sum_{i=1}^{2^n}a_i^2}{2^n}

  把aia_i拆位成bi,jb_{i,j},则答案为:

=i=12n(jmbi,j2j)22n=i=12nj=1mk=1mbi,jbi,k2j+k2n=j=1mk=1mi=12nbi,jbi,k2n2j+k\begin{aligned} &=\frac{\sum_{i=1}^{2^n}(\sum_j^mb_{i,j}2^j)^2}{2^n}\\ &=\frac{\sum_{i=1}^{2^n}\sum_{j=1}^m\sum_{k=1}^mb_{i,j}b_{i,k}2^{j+k}}{2^n}\\ &=\sum_{j=1}^m\sum_{k=1}^m\frac{\sum_{i=1}^{2^n}b_{i,j}b_{i,k}}{2^n}2^{j+k} \end{aligned}

  i=12nbi,jbi,k\sum_{i=1}^{2^n}b_{i,j}b_{i,k}是可以O(n)O(n)处理的,若j=kj=k那么这一位为11的概率为0.50.5,若jkj\neq k则这一位为11的概率为0.250.25
  k3k\geq 3时,由于答案<263<2^{63},故aik<263a_i^k<2^{63}。设ai=(2m1)a_i=(2^m-1),则有m63km\leq \frac{63}{k},所以当k3k\geq 3时,给定数字的位数一定21\leq 21位。
  那么直接求出线性基,爆搜所有方案,每种方案的概率为12k\frac{1}{2^k}
  虽然结果不会爆LLLL,但中间运算的时候可能会…所以我们需要把ansans化成ans2m×2m+ans mod 2m\left \lfloor \frac{ans}{2^m} \right \rfloor\times2^m +ans\ mod\ 2^m的形式。

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
#define ull unsigned long long
using namespace std;
const int maxn=500010, inf=1e9;
int n, k, cnt, tot;
ull ans, ans2;
ull a[maxn], w[maxn], b[maxn], c[maxn];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void solve1()
{
	bool flag=0; ull ans=0;
	if(w[0]) flag=1;
	for(int i=1;i<=63;i++)
	if(w[i]) ans+=1ll<<(i-1);
	printf("%llu", ans);
	puts(flag?".5":"");
}

inline void solve2()
{
	int lw=0; ull ans=0;
	for(int i=0;i<=32;i++)
	{
		if(w[i]>1) {if(i==0) lw++; else ans+=1ll<<(i+i-1);}
		for(int j=0;j<=32;j++)
		if(i!=j && w[i] && w[j])
		{
			if(i+j==1) lw++;
			else ans+=1ll<<(i+j-2);
		}
	}
	ans+=lw>>1; lw=lw&1;
	printf("%llu", ans);
	puts(lw?".5":"");
}

void dfs(int sum, int dep)
{
	if(dep>tot)
	{
		ull sum1=0, sum2=1;
		for(int i=1;i<=k;i++)
		{
			sum1*=sum; sum2*=sum;
			sum1+=sum2>>tot; sum2&=(1ull<<tot)-1;
		} 
		ans+=sum1; ans2+=sum2;
		ans+=ans2>>tot; ans2&=(1ull<<tot)-1;
		return;
	}
	dfs(sum, dep+1); dfs(sum^c[dep], dep+1);
}

inline void solve3()
{
	for(int i=1;i<=n;i++)
	{
		ull p=a[i];
		for(int j=21;~j;j--)
		if((p>>j)&1)
		{
			if(b[j]) p^=b[j];
			else {b[j]=p; break;}
		}
	}
	tot=0;
	for(int i=0;i<=21;i++) if(b[i]) c[++tot]=b[i];
	dfs(0, 1);
	printf("%llu", ans);
	puts(ans2?".5":"");
}

int main()
{
	read(n); read(k);
	for(int i=1;i<=n;i++) scanf("%llu", &a[i]);
	if(k<=2)
	{
		for(int i=1;i<=n;i++)
		{
			int cnt=0;
			while(a[i]) w[cnt++]+=a[i]&1, a[i]>>=1;
		}
	}
	if(k==1) solve1();
	else if(k==2) solve2();
	else solve3();
}