【CF772D】Varying Kibibits

题意：定义函数f(a,b,c...)表示将a,b,c..的10进制下的每一位拆开，分别取最小值组成的数。如f(123,321)=121,f(530, 932, 81)=30。给你一个数集$T={a_1,a_2...a_n}$，定义函数G(x)

求$G(1)\oplus G(2)\oplus ...G(999999)$。

$1\le n \le 1000000,0\le a_i \le 999999$

题解：发现f函数就是10进制下的按位与，所以我们先对原序列进行fwt。具体地说，因为上面那个式子里有平方，所以我们要维护3个东西，a[i]表示T中i的个数，b[i]=a[i]*i，c[i]=a[i]*i*i。将这三个东西都进行fwt。

怎么统计呢？我们要求的就是一个集合的所有子集的元素的完全平方和。设当前的集合为U，我们考虑其中一个元素y的贡献，如果$S\subseteq U-y$，那么y会在$S+y$和$U-S$里分别被统计，也就是说其贡献是$y\times 2^{|U|-2}(b[U]+y)$。所以总的贡献就是$2^{|U|-2}(b[U]^2+c[U])$。特判：当a[U]=1时，贡献就是c[U]；当a[U]=0时，贡献=0。

再逆fwt回去就好了。

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn=1000010;typedef long long ll;const ll P=1000000007;int n,len;ll ans;ll a[maxn],b[maxn],c[maxn],f[maxn],bt[maxn];inline int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();	return ret*f;}inline void fwt(){	int h,i;	for(h=1;h