异或

数论

---

题面

给出一个大小为$n$的非负整数集合$\{a_1,a_2,...,a_n\}$,等概率地选取$2^n$个子集中的一个，设$S$为子集中所有数的异或和$\overline{s_1s_2s_3...s_h}_{(2)}$，求所有情况$(s_1+s_2+s_3+...+s_h)^k$之和。

• $20pts\ n\leq20$
• $60pts\ k=1,2,3,4$
• $100pts\ n\leq100,h\leq63$

解析

$20pts$算法

$O(2^n)$暴搜。

$60pts$算法

先从$k=1$开始吧。
题目转化为求所有情况$s_1+s_2+s_3+...$之和。
而每位$s$为$1$（对答案有贡献）决定于子集中该位为$1$的数的个数为奇数。
于是我们可以数位分开单独讨论。

假设子集中该位为$1$的数的个数为$tot$。
则选出奇数个的方案数为$C_{tot}^1+C_{tot}^3+C_{tot}^5...$。
由于该位为$0$的数对答案没有影响，可以任选，故方案数还需乘上$2^{n-tot}$,即为该位对答案的贡献。
所有位贡献相加即可。

(然而只有$k=1$是对的，下面内容都有问题）
处理$k=4$需要化式子：

$$\sum(s_1+s_2+s_3+...+s_h)^4$$
$$=\sum(s_1+s_2+...)*(s_1+s_2+...)*(s_1+s_2+...)*(s_1+s_2+...)$$
$$=\sum\sum_{a=1}^h\sum_{b=1}^h\sum_{c=1}^h\sum_{d=1}^hs_as_bs_cs_d$$
于是枚举$a,b,c,d$，统计$s_a,s_b,s_c,s_d$四位都不为$0$的数的个数，组合数处理（当然要取奇数个）即可。
复杂度$O(h^kn)$。$k=4$时会达到$O(10^9)$。

有没有发现枚举$a=2,b=1,c=1,d=1$特别傻逼？这种情况和$a=1,b=1,c=1,d=2$一模一样。
我们强制$a,b,c,d$不降，然后乘上系数即可。（系数计算机爆算即可）
这样复杂度会除$4*3*2*1=24$，刚好能过。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll unsigned long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
 const int N=300,mod=998244853;
ll n,k,num[N],s[70][70][70][70],C[200][200],jc[200],ans;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il ll ksm(re ll x,re ll n)
{
  re ll S=1,T=x;
  while(n)
    {
      if(n&1) S=S*T%mod;
      T=T*T%mod;
      n>>=1;
    }
  return S;
}
il void solve(re ll s)
{
  re ll tot=0;
  fp(i,0,64)
    {
      if((1ll<<i)>s) break;
      if((1ll<<i)&s) ++tot;
    }
  (ans+=ksm(tot,k))%=mod;
}
il void dfs(re ll x,re ll s)
{
  if(x>n) {solve(s);return;}
  fp(i,0,1)
    if(i) dfs(x+1,s^num[x]);
    else dfs(x+1,s);
}
il void check(re int *a)
{
   sort(a+1,a+5);
   s[a[1]][a[2]][a[3]][a[4]]++;
}
il void Pre()
{
    re int p[5];
    C[0][0]=1;
    fp(i,1,n)
    {
        C[i][0]=1;
        fp(j,1,i) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    jc[0]=1;fp(i,1,n) jc[i]=(jc[i-1]<<1)%mod;
    fp(a,0,63) fp(b,0,63) fp(c,0,63) fp(d,0,63) p[1]=a,p[2]=b,p[3]=c,p[4]=d,check(p);
}
int main()
{
  freopen("xor.in","r",stdin);
  freopen("xor.out","w",stdout);
  n=gi();k=gi();
  fp(i,1,n) num[i]=gi();
  if(n<=20) dfs(1,0);
  else if(k==1)
    {
        Pre();
        fp(a,0,63)
        {
            re ll tot=0,sum=0;
            fp(i,1,n) 
                if(num[i]&(1ll<<a)) ++tot;
            for(re int i=1;i<=tot;i+=2) (sum+=C[tot][i])%=mod;
            sum=sum*jc[n-tot]%mod;
            (ans+=sum)%=mod;
        }
    }
  else if(k==2)
    {
         Pre();
        fp(a,0,63)
        fp(b,0,63)
        {
            re ll tot=0,sum=0;
            fp(i,1,n) 
          if((num[i]&(1ll<<a))&&(num[i]&(1ll<<b))) ++tot;
            for(re int i=1;i<=tot;i+=2) (sum+=C[tot][i])%=mod;
            sum=sum*jc[n-tot]%mod;
            (ans+=sum)%=mod;
        }
    }
  else if(k==3)
    {
      Pre();
        fp(a,0,63)
        fp(b,0,63)
        fp(c,0,63)
        {
            re ll tot=0,sum=0;
            fp(i,1,n) 
                if((num[i]&(1ll<<a))&&(num[i]&(1ll<<b))&&(num[i]&(1ll<<c))) ++tot;
            for(re int i=1;i<=tot;i+=2) (sum+=C[tot][i])%=mod;
            sum=sum*jc[n-tot]%mod;
            (ans+=sum)%=mod;
        }
    }
  else if(k==4)
    {
      Pre();
        fp(a,0,63)
        fp(b,a,63)
        fp(c,b,63)
        fp(d,c,63)
        {
            re ll tot=0,sum=0;
            fp(i,1,n) 
                if((num[i]&(1ll<<a))&&(num[i]&(1ll<<b))&&(num[i]&(1ll<<c))&&(num[i]&(1ll<<d))) ++tot;
            for(re int i=1;i<=tot;i+=2) (sum+=C[tot][i])%=mod;
            sum=sum*jc[n-tot]%mod;
            (ans+=sum)%=mod;
        }
    }
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}