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了。代码:

2 条评论
  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.

  2. Thank you for all of the hard work on this blog. Gloria loves managing investigation and it is simple to grasp why. A number of us know all about the lively form you deliver practical tips via the web blog and even strongly encourage response from some other people on this concept plus our princess is truly understanding a lot of things. Have fun with the rest of the new year. Your doing a very good job.

发表一条评论