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; 
}

Leave a Comment

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