# luoOJ1898 运动会（Race）题解

[题目传送门][1]

$\displaystyle\sum_{sta\subseteq \lbrace 1,2,3,…,m \rbrace }{(\displaystyle\sum_{i=1}^{m}{[i\in sta]p[i]})^2}$

$\displaystyle\sum_{sta\subseteq \lbrace 1,2,3,…,m-1 \rbrace }{(p[m]+\displaystyle\sum_{i=1}^{m-1}{[i\in sta]p[i]})^2}+\displaystyle\sum_{sta\subseteq \lbrace 1,2,3,…,m-1 \rbrace }{(\displaystyle\sum_{i=1}^{m-1}{[i\in sta]p[i]})^2}$

$2^{m-1}p[m]^2+2p[m]\displaystyle\sum_{sta\subseteq \lbrace 1,2,3,…,m-1 \rbrace }{\displaystyle\sum_{i=1}^{m-1}{[i\in sta]p[i]}}+2\displaystyle\sum_{sta\subseteq \lbrace 1,2,3,…,m-1 \rbrace }{(\displaystyle\sum_{i=1}^{m-1}{[i\in sta]p[i]})^2}$

#include<cstdio>
#include<algorithm>
#define MAX_N 200005
#define MAX_M 35
#define MOD 1000000007
using namespace std;
struct Node{ int son[2]; int size; };
Node tree[MAX_N*MAX_M];
int n,m,top_tree=-1;
int new_node(){
++top_tree;
tree[top_tree].size=0;
tree[top_tree].son[0]=-1;
tree[top_tree].son[1]=-1;
}
void insert(int key){
int x=0; ++tree[0].size;
for(int i=m-1;i>=0;--i){
bool type=(key&(1<<i))>0;
if(tree[x].son[type]==-1) tree[x].son[type]=new_node();
x=tree[x].son[type];
++tree[x].size;
}
}
void initialize(){
scanf("%d%d",&n,&m);
new_node();
for(int i=0;i<n;++i){
int key; scanf("%d",&key);
insert(key);
}
}
long long p[MAX_M],f[MAX_M],s[MAX_M],ans=0;
void compute(){
s[0]=0,f[0]=0;
for(int i=1;i<=m;++i) s[i]=s[i-1]+p[i];
for(int i=1;i<=m;++i)
f[i]=((1<<(i-1))*(p[i]*p[i]%MOD)+(1<<(i-1))*p[i]%MOD*s[i-1]+2*f[i-1])%MOD;
ans^=f[m];
}
void dfs(int x,int depth){
if(x==-1) return;
if(tree[x].son[0]==-1&&tree[x].son[1]==-1) compute();
for(int i=0;i<2;++i){
p[depth+1]=(tree[x].son[i^1]==-1)?0:tree[tree[x].son[i^1]].size;
dfs(tree[x].son[i],depth+1);
}
}
int main(){
initialize();
dfs(0,0);
printf("%lld",ans);
return 0;
}


### 1 thought on “luoOJ1898 运动会（Race）题解”

1. I not to mention my guys came checking out the great items from the website and then the sudden got a terrible feeling I never expressed respect to the site owner for those secrets. Those women are already for that reason excited to learn all of them and have in effect honestly been taking advantage of those things. Many thanks for getting well considerate and then for opting for some marvelous themes millions of individuals are really needing to understand about. Our honest regret for not expressing gratitude to sooner.