luoOJ1898 运动会(Race)题解

[题目传送门][1]
我看到题一脸懵逼,感觉一点思路都没有,然后想了6个小时,搞出来了一个很复杂的一堆前缀和的做法,然后错了。最后我发现其实不需要这么复杂,这题其实是一道水题,我们可以进行一些简单的分析来A了它。
由于每天各个人的分数是异或产生的,很容易想到搞一棵字典树。我又发现对于每一个人,它既要取模又要异或,肯定不会一起来算,因此可以把每一个人的得分分开来考虑。
然后我发现,在字典树中对于每一条通向某人A得分的路径上每一层的另外一棵子树中的人总是一起出现在A排名的前面或者后面,而且前面后面的机会都各占一半。因此我们不妨将这些子树中的人数依次记为(易得有m棵)p[1],p[2],p[3]…p[m](如果没有子树则记为0)。
然后根据题意列出式子(得到A对答案的贡献,为方便表示不取模):
$\displaystyle\sum_{sta\subseteq \lbrace 1,2,3,…,m \rbrace }{(\displaystyle\sum_{i=1}^{m}{[i\in sta]p[i]})^2}$
这里面sta枚举的是那些层的另一侧子树在该人排名的前面,由于排名从0开始,因此只需要将这些再它前面的人的个数加起来再平方即可。显然直接暴力算一次这个东西需要的时间为$\Theta(m2^m)$。然而这东西有个鬼畜的性质。
我们枚举sta中是否有m这个元素,然后就得到了下面这个式子:
$\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}$
我们可以依次来分析这三个用加号连接的部分。第一个部分直接算,没什么好说的,第二个部分可以通过一些简单的预处理来计算(因为每一个p[i]被加的次数是一样的),第三个部分是一个与原问题形式相同规模更小的问题,我们可以递归(递推)求解。
然后就得到了一个字典树上跑一跑再预处理+递推的做法,时间复杂度$\Theta(nm)$。然后我就AC了。代码:

#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;
    return top_tree;
}
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.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注