相关链接
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4624
神犇题解Ⅰ：http://www.cnblogs.com/chanme/p/4869377.html
神犇题解Ⅱ：http://blog.csdn.net/beginendzrq/article/details/51331954
解题报告
我们设$f_i$为染色$i$次后还有球没有被染色的概率
那么我们的答案$ans$为： $\sum\limits_{i = 0}^\infty {{f_i}} $
现在考虑如何求$f_i$，我们先来$O(2^n)$暴力容斥
具体来讲，我们枚举染色$i$次后还剩下哪些球为白色
设还有$k$个球为白色，这$k$个球位置分别为$v_1 \sim v_k$
那么单次染色的区间不能包含这$k$个位置，设合法的方案数为$A$
那么单次染色符合条件的概率$P=\frac{A}{\frac{n(n-1)}{2}}$
那么$i$次都符合要求的概率就是$P^i$
于是对于$f_i$来讲，贡献为$P^i \cdot (-1)^{k-1}$
这种情况对于答案$ans$的贡献为$(-1)^{k-1}\sum\limits_{i=0}^{\infty}{P^i}=\frac{(-1)^{k-1}}{1-P}$
现在考虑优化容斥的过程
我们发现每一种具体的方案对于答案的贡献只与剩余球的数量的奇偶性和$A$有关
于是我们可以搞一个状态为$O(n^4)$，转移为$O(1)$的DP来优化容斥
Code
这份代码在我本地跑出来是对的，但交上去就wa
于是只能打了一份表交上去：http://paste.ubuntu.com/24448347/
#include<bits/stdc++.h>
#define LL long long
#define LDB __float128
using namespace std;
const int N = 51;
const int M = N * N;
int n,ww,pp;
LL f[2][N][M][2];
LDB ans;
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
int main() {
for (int T=read();T;T--) {
ans = ww = 0; pp = 1;
memset(f,0,sizeof(f));
f[pp][0][0][0] = 1;
n = read();
for (int i=0;i<n;i++,ww^=1,pp^=1) {
memset(f[ww],0,sizeof(f[ww]));
for (int j=0;j<=i;j++) {
for (int k=i*i;~k;k--) {
for (int p=0;p<=1;p++) {
if (f[pp][j][k][p]) {
f[ww][0][k+j*(j+1)/2][p^(j&1)] += f[pp][j][k][p];
f[ww][j+1][k][p] += f[pp][j][k][p];
}
}
}
}
}
for (int j=0;j<=n;j++) {
for (int k=n*n;~k;k--) {
for (int p=0;p<=1;p++) {
if (!f[pp][j][k][p]) continue;
int v = k + j * (j + 1) / 2, t = p ^ (j & 1);
LDB tmp = ((v < n * (n + 1) / 2)? ((LDB)v / (n * (n + 1) / 2 - v)): 0);
if ((n-t)&1) ans += tmp * f[pp][j][k][p];
else ans -= tmp * f[pp][j][k][p];
}
}
}
ans += 1;
printf("%.15Lf\n",(long double)ans);
}
return 0;
}
相关拓展
当然这题还可以改成：如果染到$k$个球都为黑色了就停止，询问停止时的期望步数
例题可以参考：凯旋三兵
哇塞，居然是沙发？留个名
I’m not that much of a online reader to be honest but your sites
really nice, keep it up! I’ll go ahead and bookmark your site
to come back down the road. All the best
Nice response in return of this difficulty
with solid arguments and telling everything on the topic of that.
Wow that was strange. I just wrote an very long comment but after I clicked submit my
comment didn’t show up. Grrrr… well I’m not
writing all that over again. Anyway, just wanted to say excellent blog!
Sweet blog! I found it while surfing around on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Cheers
I am regular visitor, how are you everybody? This article posted at this web page is genuinely good.
I do not know whether it’s just me or if perhaps everyone else experiencing issues with your site.
It seems like some of the written text on your posts are running off the screen. Can someone else please comment
and let me know if this is happening to them as well? This might be a problem with my
web browser because I’ve had this happen previously.
Cheers
Aw, this was an exceptionally nice post. Finding the time and actual effort to create a superb article… but what can I
say… I procrastinate a lot and don’t manage to get anything done.
After I originally commented I appear to have clicked the -Notify me when new comments are added-
checkbox and now each time a comment is added I recieve four emails
with the same comment. There has to be a way you are able to remove me from that service?
Thanks a lot!
I’ve been surfing online more than 3 hours today, yet I never found
any interesting article like yours. It is pretty worth enough for me.
Personally, if all web owners and bloggers made good
content as you did, the net will be a lot more useful than ever before.
This article is in fact a fastidious one it assists new internet viewers, who are wishing in favor of blogging.
Great post however I was wanting to know if you could write a litte more on this subject?
I’d be very thankful if you could elaborate a little bit
more. Bless you!
Sweet blog! I found it while searching on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Thank you
I’m not sure exactly why but this web site is loading
very slow for me. Is anyone else having this problem
or is it a problem on my end? I’ll check back later and see if
the problem still exists.
I seriously love your website.. Pleasant colors &
theme. Did you create this website yourself?
Please reply back as I’m wanting to create my very own website
and want to know where you got this from or just what the
theme is called. Many thanks!
Great blog you have got here.. It’s difficult to
find quality writing like yours these days. I really appreciate people
like you! Take care!!
After I initially left a comment I appear to have clicked the -Notify me when new comments are
added- checkbox and from now on each time a comment is added I
receive four emails with the same comment. Perhaps there is a way you can remove me from that service?
Many thanks!
A person necessarily assist to make critically posts I’d state.
This is the very first time I frequented your web page
and to this point? I amazed with the analysis you
made to create this actual submit extraordinary.
Magnificent process!
My spouse and I absolutely love your blog and find nearly all of your post’s to
be just what I’m looking for. can you offer guest writers to write content available for you?
I wouldn’t mind producing a post or elaborating
on most of the subjects you write concerning here. Again, awesome blog!
pof natalielise
Hello, I would like to subscribe for this website to get
latest updates, thus where can i do it please assist.
Hey there! I know this is kind of off topic but I was wondering if you
knew where I could locate a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having trouble finding one?
Thanks a lot! pof natalielise
I know this if off topic but I’m looking into starting my own blog and was wondering what all is needed to get set up?
I’m assuming having a blog like yours would cost a pretty penny?
I’m not very web savvy so I’m not 100% positive. Any tips or advice would be
greatly appreciated. Many thanks
Really when someone doesn’t be aware of after that its
up to other visitors that they will assist, so here
it occurs.
I really like looking through a post that can make people think.
Also, thank you for allowing me to comment! pof natalielise
I used to be able to find good information from your articles.
natalielise plenty of fish
I have read so many content on the topic of the blogger
lovers except this piece of writing is in fact a pleasant piece
of writing, keep it up.
Excellent way of explaining, and nice paragraph to get data about
my presentation topic, which i am going to present in school.
May I simply just say what a comfort to discover someone who truly knows what they’re talking
about over the internet. You certainly understand how to bring an issue to light and make it important.
More and more people really need to check this out and understand this side of your story.
I was surprised that you aren’t more popular because you certainly have the gift.
I’m not sure why but this website is loading very slow for me.
Is anyone else having this problem or is it a problem on my end?
I’ll check back later on and see if the problem still exists.
magnificent put up, very informative. I’m wondering why the
opposite experts of this sector don’t notice this. You should continue your writing.
I am confident, you’ve a great readers’ base already!
Appreciating the time and energy you put into your website and detailed information you present.
It’s great to come across a blog every once
in a while that isn’t the same unwanted rehashed material.
Wonderful read! I’ve saved your site and I’m including your RSS feeds to my Google account.
I used to be suggested this website through my cousin. I’m no longer positive whether or not
this submit is written by way of him as no one else know such
specified about my difficulty. You are wonderful!
Thanks!
After looking at a number of the blog articles on your web page, I honestly like your way
of writing a blog. I added it to my bookmark
webpage list and will be checking back in the near future.
Take a look at my web site as well and let me know your opinion.
I always spent my half an hour to read this blog’s posts every day
along with a mug of coffee.
Wonderful blog! I found it while browsing on Yahoo News.
Do you have any tips on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem to get there!
Cheers
I absolutely love your website.. Pleasant colors & theme.
Did you develop this amazing site yourself?
Please reply back as I’m attempting to create my
own personal website and would love to find out where you got this from
or what the theme is named. Cheers!
Its such as you read my mind! You appear to know so much approximately this,
like you wrote the e book in it or something. I think that you could do with some percent to force
the message house a little bit, but instead of that, this is magnificent blog.
An excellent read. I will definitely be back.
Hmm it appears like your site ate my first comment (it was extremely long) so I guess I’ll just
sum it up what I wrote and say, I’m thoroughly enjoying your blog.
I too am an aspiring blog writer but I’m still new to the whole thing.
Do you have any tips and hints for beginner
blog writers? I’d genuinely appreciate it.
I have learn some just right stuff here. Certainly price bookmarking for revisiting.
I wonder how so much attempt you place to create the sort
of magnificent informative website.
Hi! Do you use Twitter? I’d like to follow you if
that would be ok. I’m definitely enjoying your blog
and look forward to new posts.
Hi there everyone, it’s my first go to see at this website, and paragraph is really fruitful in favor of me,
keep up posting these types of articles or reviews.
Keep on working, great job!
I was wondering if you ever considered changing the
page layout of your website? Its very well written; I love what youve got
to say. But maybe you could a little more in the way of content so
people could connect with it better. Youve got an awful lot of text for only having 1 or
2 pictures. Maybe you could space it out better?
If you would like to obtain much from this
post then you have to apply such methods to your won blog.
Thank you for sharing your thoughts. I really appreciate your efforts and I am waiting for your further write ups thanks once again.
You have made some good points there. I checked on the net for more
information about the issue and found most people will go along with your views on this
website.
Thanks a bunch for sharing this with all of us you really recognise what you are speaking about!
Bookmarked. Please additionally discuss with my web site =).
We can have a hyperlink change agreement between us
After looking into a number of the blog articles on your
site, I seriously appreciate your technique of blogging. I bookmarked it to my bookmark
website list and will be checking back soon. Please check out my web site as
well and let me know your opinion.
This paragraph is in fact a good one it assists new web people,
who are wishing for blogging.
Does your blog have a contact page? I’m having trouble locating it but,
I’d like to send you an e-mail. I’ve got some creative ideas for your blog you might be interested in hearing.
Either way, great website and I look forward to seeing it expand over
time.
Its not my first time to pay a quick visit this web page, i am visiting this website dailly and obtain pleasant facts from here everyday.
Very good blog you have here but I was wanting to know if
you knew of any user discussion forums that cover the same
topics talked about in this article? I’d really like to be a part of community where I can get suggestions from other knowledgeable people
that share the same interest. If you have any suggestions, please let me know.
Thanks!
I really like your blog.. very nice colors & theme. Did you make this
website yourself or did you hire someone to do
it for you? Plz respond as I’m looking to construct
my own blog and would like to find out where u got this from.
thank you
Hi there to all, how is all, I think every one is getting more
from this web site, and your views are fastidious in favor
of new users.
For hottest information you have to pay a quick
visit internet and on world-wide-web I found this site
as a finest website for most up-to-date updates.
It is appropriate time to make some plans for the future and it is time to be
happy. I’ve read this post and if I could I want to suggest you few interesting things or suggestions.
Maybe you can write next articles referring to this article.
I want to read more things about it!
Quality articles or reviews is the main to
attract the viewers to pay a quick visit the web
site, that’s what this website is providing.
Hi there would you mind letting me know which hosting company you’re utilizing?
I’ve loaded your blog in 3 different web browsers and I must say this blog loads a lot faster then most.
Can you suggest a good hosting provider at a honest price? Kudos, I appreciate it!
I just like the helpful information you supply to your articles.
I will bookmark your weblog and check once more right here regularly.
I am quite certain I’ll be told many new stuff proper here!
Good luck for the next!
Pretty section of content. I just stumbled upon your blog and in accession capital to assert that I acquire actually enjoyed account your blog posts.
Anyway I will be subscribing to your feeds and even I achievement you access
consistently rapidly.
Hi to every one, the contents existing at this website are
in fact remarkable for people knowledge, well, keep up the good work fellows.
Hello! I could have sworn I’ve been to this website before but after browsing through some of the posts I realized it’s
new to me. Regardless, I’m certainly delighted I found
it and I’ll be bookmarking it and checking back often!
Unquestionably believe that which you said. Your favorite justification seemed
to be on the internet the simplest thing to be aware of.
I say to you, I definitely get annoyed while people consider worries that they plainly don’t know about.
You managed to hit the nail upon the top and also defined out
the whole thing without having side effect , people can take a signal.
Will likely be back to get more. Thanks
What’s up everyone, it’s my first visit at this web site, and paragraph is truly fruitful designed
for me, keep up posting these types of articles
or reviews.
I’m gone to tell my little brother, that he should also go to see
this blog on regular basis to get updated from most up-to-date news update.
It’s hard to come by educated people for this topic, however, you sound like you know what you’re talking
about! Thanks
Right now it looks like Expression Engine is the best blogging platform out there right now.
(from what I’ve read) Is that what you are using on your
blog?
Way cool! Some very valid points! I appreciate you writing this article and the rest of the website is also very
good.
Hey! Would you mind if I share your blog with my myspace group?
There’s a lot of folks that I think would really appreciate
your content. Please let me know. Thank you
Your style is really unique compared to other
folks I’ve read stuff from. I appreciate you for posting when you’ve got the opportunity, Guess I will just
bookmark this site.
Perfect work you have done, this internet site is really cool with superb information.
You could certainly see your enthusiasm in the article you write.
The sector hopes for more passionate writers like you who are not afraid to mention how they believe.
At all times follow your heart.
What i don’t realize is actually how you are now not really a lot more well-preferred
than you may be now. You are so intelligent. You know
thus considerably when it comes to this topic, produced me individually believe it from numerous numerous angles.
Its like men and women are not interested unless it is something to accomplish with Lady gaga!
Your individual stuffs excellent. All the time take care of it up!
Thanks for your personal marvelous posting!
I truly enjoyed reading it, you are a great author.
I will ensure that I bookmark your blog and may come back someday.
I want to encourage you to ultimately continue your great writing, have a nice day!
Great post! We are linking to this great article on our website.
Keep up the good writing.
It is not my first time to pay a visit this web page, i am browsing this web page dailly and
obtain nice data from here every day.
Awesome blog! Is your theme custom made or did you download
it from somewhere? A theme like yours with a few simple
tweeks would really make my blog stand out. Please let me
know where you got your theme. Thanks a lot
We are a group of volunteers and starting a new scheme in our community.
Your site offered us with valuable info to work on. You’ve done a formidable job
and our whole community will be grateful to you.
Link exchange is nothing else however it is
simply placing the other person’s web site
link on your page at proper place and other person will
also do similar for you.
Hello, I enjoy reading through your article post. I wanted to write
a little comment to support you.
Heya i’m for the first time here. I found this board and I find It really useful & it helped me out much.
I hope to give something back and aid others like
you aided me.
Hi colleagues, how is everything, and what you wish for to
say about this article, in my view its actually awesome designed
for me.
Somebody necessarily lend a hand to make significantly articles I
might state. That is the first time I frequented your web page
and so far? I amazed with the research you made to make this actual post extraordinary.
Great activity!
What’s Happening i am new to this, I stumbled upon this I have found It positively helpful and it has helped me out loads. I hope to contribute & help other users like its aided me. Good job.