相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3811
神犇题解Ⅰ：https://blog.sengxian.com/solutions/bzoj-3811
神犇题解Ⅱ：http://yyy.is-programmer.com/posts/200623.html
解题报告
这题这么神，我们来分情况讨论：
1. $k = 1$
这就是一般的期望题。因为期望的线性，所以我们在二进制位下每一位分开考虑：
如果这一位上每一个数都是$0$，那么贡献肯定为$0$
如果有一个数为不为$0$那么我们有贡献的概率为$\frac{1}{2}$
证明的话，可以设$f_{1,0/1}$为考虑到第i个数，异或起来为0/1的概率
写出$DP$式子可以很轻松地发现这俩总是对半分，Q.E.D
于是我们直接把所有数$or$起来，然后除二输出即可
时间复杂度：$O(n)$
2. $k = 2$
这不是一般的期望题了，不是线性的，不能直接加 /(ㄒoㄒ)/~~
但我们发现某一个异或和为$(b_mb_{m-1} \cdots b_0)_{bin}$的话
其中第$i$位与第$j$位的贡献为$b_i \cdot b_j \cdot 2^{i+j}$
因为$b_i$与$b_j$是线性的，所以我们就可以枚举$i,j$然后直接加起来了！
根据$k = 1$时得到的结论，不难发现：
如果这两位独立则贡献的概率为$\frac{1}{4}$
如果这两位不独立，那么贡献的概率为$\frac{1}{2}$
如果这两位中有至少一位从没出现过，那么概率为$0$
于是我们暴力枚举$i,j$直接算贡献就可以了
时间复杂度：$O(62n + 62^2)$
3. $k \ge 3$
我们先来看一个结论：若$E(x^k) < 2^{63}$，初始集合中的每个数小于$2^{22}$
证明的话，sengxian教我的：
不妨用反证法，考虑答案为：$\sum\limits_{s \in \{1,2,\cdots,n\}}{\frac{v^3}{2^n}}$
假如有一个数的二进制下第$22$位出现了$1$，有$2^{n-1}$个集合异或起来后这一位为$1$
所以这一位的贡献就已经为$2^{63}$了，又因为答案小于$2^{63}$，矛盾，故不可能，Q.E.D
所以我们可以求出这些数的线性基，然后暴力枚举线性基的子集
根据$k = 1$时的人生经验，我们又可以得到每一种情况出现的概率相等
于是我们暴力枚举，然后暴力算贡献就可以了
时间复杂度：$O(21n + 2^{21})$
Wow, that’s what I was looking for, what a information! existing here at this blog,
thanks admin of this web page.
I enjoy reading an article that can make men and women think.
Also, thank you for allowing me to comment!
Hi there this is kind of of off topic but I was wondering if blogs
use WYSIWYG editors or if you have to manually
code with HTML. I’m starting a blog soon but have no coding skills so I wanted to get guidance from someone with experience.
Any help would be enormously appreciated!
I’m very happy to discover this site. I want to to thank you for
your time for this particularly fantastic
read!! I definitely appreciated every little bit of it and I have you saved to fav to
check out new information in your site.
Yesterday, while I was at work, my cousin stole my
apple ipad and tested to see if it can survive a 25 foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is completely off topic but I had to share it with
someone!
Having read this I believed it was very informative. I appreciate you
spending some time and energy to put this informative article together.
I once again find myself personally spending way too much time both reading
and commenting. But so what, it was still worth
it!
I think that is among the most vital information for me.
And i am glad reading your article. But want to remark on few normal things,
The website style is great, the articles is really
nice : D. Good process, cheers
Today, I went to the beach front with my children. I
found a sea shell and gave it to my 4 year old daughter
and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
There was a hermit crab inside and it pinched
her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!
Undeniably consider that that you stated. Your favourite reason seemed to be on the internet
the easiest factor to have in mind of. I say to you,
I definitely get annoyed whilst other folks consider worries that
they just do not recognise about. You controlled to hit the nail
upon the highest and also defined out the whole thing without having side effect , other
folks could take a signal. Will likely be back to get more.
Thanks
This design is steller! You definitely know how to keep
a reader entertained. Between your wit and your videos, I was almost moved to start my own blog
(well, almost…HaHa!) Great job. I really loved what you had to say, and more than that, how you presented it.
Too cool!
It’s perfect time to make some plans for the future
and it is time to be happy. I have read this post and if I could I want to suggest you some interesting things or tips.
Maybe you could write next articles referring to this article.
I want to read even more things about it!
This paragraph is in fact a nice one it helps new net visitors, who are wishing in favor of
blogging.
You actually make it appear really easy with your presentation however I
to find this topic to be actually something which I believe I’d never understand.
It kind of feels too complicated and very wide for me. I’m having a look forward for your subsequent publish, I
will attempt to get the grasp of it!
Wow, this paragraph is fastidious, my sister is analyzing these kinds of things, so I am going to inform her.
Heya i’m for the first time here. I found this board
and I to find It truly helpful & it helped me out a lot.
I’m hoping to offer one thing back and help
others like you helped me.
What’s up, I wish for to subscribe for this webpage to get newest
updates, therefore where can i do it please help out.
Right here is the perfect webpage for everyone who wants to find out about this topic.
You realize so much its almost tough to argue with you (not that I really would
want to…HaHa). You certainly put a fresh spin on a topic that’s
been written about for decades. Wonderful stuff,
just wonderful!
After all, what a great site and informative posts, I will upload inbound link – bookmark this web site? Regards, Reader.
Thank you a bunch for sharing this with all of us
you actually know what you are speaking about! Bookmarked.
Please also visit my web site =). We can have
a link change agreement among us
Greetings! Very helpful advice within this article! It’s the little changes that produce the most significant changes.
Thanks a lot for sharing!
It’s an amazing piece of writing designed for all the online people;
they will take benefit from it I am sure.
Excellent post. I was checking constantly this
blog and I’m impressed! Very useful information particularly the last part :
) I care for such info a lot. I was looking for this particular information for
a long time. Thank you and good luck.
I have read so many articles on the topic of the blogger lovers however this article
is genuinely a fastidious paragraph, keep it up.
Hello to every single one, it’s really a good for me to go to
see this web page, it contains priceless Information.
Write more, thats all I have to say. Literally, it seems as though
you relied on the video to make your point.
You clearly know what youre talking about, why throw away
your intelligence on just posting videos to your blog
when you could be giving us something enlightening to read?
Yes! Finally someone writes about sling tv.
Pretty nice post. I just stumbled upon your weblog and wished to say that I’ve really enjoyed surfing
around your blog posts. In any case I’ll be subscribing to your rss feed
and I hope you write again soon!
For most recent information you have to go to see internet and on internet I found this web site as a finest web site for newest updates.
Magnificent items from you, man. I’ve understand your stuff prior to and you are simply too excellent. I really like what you’ve got here, really like what you are saying and the way in which by which you are saying it. You make it enjoyable and you continue to care for to stay it sensible. I can not wait to learn far more from you. That is really a wonderful web site.