【CF772D】Varying Kibibits FWT
2023-09-11 14:15:24 时间
【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 <cstdio>
#include <cstring>
#include <iostream>
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<len;h*=10)
{
for(i=len-1;~i;i--) if(i/h%10)
{
a[i-h]=(a[i-h]+a[i])%P;
b[i-h]=(b[i-h]+b[i])%P;
c[i-h]=(c[i-h]+c[i])%P;
}
}
}
inline void ufwt()
{
int h,i;
for(h=1;h<len;h*=10)
{
for(i=0;i<len;i++) if(i/h%10)
{
f[i-h]=(f[i-h]-f[i]+P)%P;
}
}
}
int main()
{
n=rd();
int i;
ll x;
for(i=1;i<=n;i++) x=rd(),a[x]++,b[x]=(b[x]+x)%P,c[x]=(c[x]+x*x)%P;
len=1000000;
fwt();
for(bt[0]=i=1;i<=n;i++) bt[i]=(bt[i-1]<<1)%P;
for(i=0;i<len;i++)
{
if(!a[i]) continue;
if(a[i]==1) f[i]=c[i];
else f[i]=bt[a[i]-2]*(b[i]*b[i]%P+c[i])%P;
}
ufwt();
for(i=0;i<len;i++) ans^=f[i]*i;
printf("%lld",ans);
return 0;
}