相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4318
神犇题解:https://oi.men.ci/bzoj-4318/
解题报告
设$p_i$为第$i$个操作成功的概率
设$E_{(i,x^3)}$为以第$i$个位置为结尾,$($极长$1$的长度$x)^3$的期望
$E_{(i,x^2)},E_{(i,x)}$分别表示$x^2,x$的期望
那么根据全期望公式,我们有如下结论:
$E_{(i,x^3)}=p_i \times E_{(i-1,(x+1)^3)}$
$E_{(i,x^2)}=p_i \times E_{(i-1,(x+1)^2)}$
$E_{(i,x)}=p_i \times (E_{(i-1,x)} + 1)$
不难发现只有第三个式子可以直接算
但我们还知道一个东西叫期望的线性,于是我们可以将前两个式子化为:
$E_{(i,x^3)}=p_i \times (E_{(i-1,x^3)} + 3E_{(i-1,x^2)} + 3E_{(i-1,x)} + 1)$
$E_{(i,x^2)}=p_i \times (E_{(i-1,x^2)} + 2E_{(i-1,x)} + 1)$
然后就可以直接维护,然后再根据期望的线性加入答案就可以辣!
时间复杂度:$O(n)$
另外,似乎直接算贡献也可以?
可以参考:http://blog.csdn.net/PoPoQQQ/article/details/49512533
Code
#include<bits/stdc++.h> #define LL long long using namespace std; 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() { int n=read(); double e1=0,e2=0,e3=0,ans=0,p; for (int i=1;i<=n;i++) { scanf("%lf",&p); ans += e3 * (1 - p); e3 = p * (e3 + 3 * e2 + 3 * e1 + 1); e2 = p * (e2 + 2 * e1 + 1); e1 = p * (e1 + 1); } printf("%.1lf\n",ans+e3); return 0; }
Hi, great work. I really appeaciate the information you are providing through your site, i have alwasy find it helpful. Keep up the amazing work.
I must thank you for the efforts you’ve put in penning this website. I am hoping to see the same high-grade content by you later on as well. In truth, your creative writing abilities has encouraged me to get my very own blog now 😉
Hi there, I found your website via Google while looking for a related topic, your web site came up, it looks great. I’ve bookmarked it in my google bookmarks.
Fantastic article.Much thanks again. Really Great.
A round of applause for your blog.Really looking forward to read more. Fantastic.
This is one awesome article.Really thank you! Cool.
Really appreciate you sharing this article.Really thank you! Cool.
I appreciate you sharing this blog post.Thanks Again. Cool.
Thank you for your blog.Really thank you! Great.
Really appreciate you sharing this blog.Much thanks again. Keep writing.
A big thank you for your post.Much thanks again. Great.
A round of applause for your post.Really looking forward to read more. Will read on…
Awesome article. Cool.
wow, awesome blog post.Really thank you! Much obliged.
Thanks-a-mundo for the post.Really thank you! Want more.
I loved your article. Fantastic.
Awesome article.Really looking forward to read more. Awesome.
A big thank you for your article post.
Enjoyed every bit of your blog post.Really thank you! Great.
Great blog.Really looking forward to read more. Really Great.
Major thankies for the article post.Really looking forward to read more. Great.
Fantastic post.Really looking forward to read more. Cool.
Really appreciate you sharing this blog article.Much thanks again. Will read on…
Great article.Thanks Again. Great.
Really enjoyed this article.Really looking forward to read more. Really Cool.
Appreciate you sharing, great article.Really looking forward to read more. Awesome.
I loved your article.Really thank you! Cool.
Thanks for the article post. Keep writing.
I really liked your article.Really looking forward to read more. Cool.
I truly appreciate this post.Really thank you! Much obliged.
I loved your article post.Really looking forward to read more. Fantastic.
Looking forward to reading more. Great article post.Really looking forward to read more.
Major thankies for the article post.Really thank you!
Really informative blog post. Want more.
A big thank you for your article.Really looking forward to read more. Much obliged.
This is one awesome article.Really thank you! Keep writing.
A round of applause for your post.Really thank you! Awesome.
This is one awesome blog post. Much obliged.
Really enjoyed this article post. Great.
A round of applause for your blog.Really thank you! Much obliged.
A big thank you for your blog article.Really looking forward to read more.
I absolutely love your blog and find almost all of your post’s
to be what precisely I’m looking for. can you offer guest writers to write content in your case?
I wouldn’t mind writing a post or elaborating on most of the subjects you write related to here.
Again, awesome web site!
Muchos Gracias for your article post.Thanks Again. Want more.
After I initially left a comment I appear to have clicked on the -Notify me when new comments are added- checkbox and from now on whenever a comment is added I get 4 emails with the same comment.
Perhaps there is an easy method you can remove me from that
service? Thanks a lot!
Im obliged for the article.Really thank you! Awesome.
Thanks again for the post. Really Great.
I do not even know how I ended up here, but I thought this post was great.
I don’t know who you are but definitely you are going to a famous
blogger if you aren’t already 😉 Cheers!
I truly appreciate this post. I have been looking everywhere for this
Great, thanks for sharing this blog post.Much thanks again. Cool.
Great article.Really thank you! Will read on…
Appreciate you sharing, great blog.Really looking forward to read more. Will read on…
Very neat blog post.Really looking forward to read more. Want more.
Major thanks for the blog.Thanks Again. Really Cool.
Looking forward to reading more. Great blog article.Really looking forward to read more. Fantastic.
Very informative post.Thanks Again. Will read on…
What’s up to all, how is the whole thing, I think every one is getting more from this site,
and your views are nice in support of new visitors.
Thank you ever so for you blog.Thanks Again. Much obliged.
I truly appreciate this post. I have been looking everywhere for this
I really like and appreciate your article. Keep writing.
I pay a visit each day some web pages and information sites to read
content, but this webpage presents quality based writing.
Thanks a lot for the blog article.Thanks Again. Great.
Hi, I read your blogs on a regular basis. Your story-telling style is awesome,
keep it up!
Enjoyed every bit of your article.Thanks Again. Really Cool.
I value the blog. Want more.
Thanks a lot for the article. Really Cool.
I really like and appreciate your blog.Thanks Again. Really Great.
Thanks so much for the article post.Really thank you! Keep writing.
Great, thanks for sharing this blog.Really looking forward to read more. Great.
Say, you got a nice blog article. Will read on…
Your writing taste has been surprised me. Thank you, quite nice post.
Really informative post.Much thanks again. Really Cool.
This is one awesome blog article. Awesome.
Thank you for your blog. Want more.
Fantastic blog article.Really looking forward to read more. Keep writing.
Thank you for your blog article.Really thank you! Really Cool.
Thanks so much for the blog post. Want more.
This is one awesome blog article.Much thanks again. Really Great.
Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my
blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some time and was hoping maybe
you would have some experience with something
like this. Please let me know if you run into anything.
I truly enjoy reading your blog and I look forward to your new
updates.
Major thanks for the blog post.Much thanks again. Want more.
I really liked your blog.Really thank you! Will read on…
First of all I want to say excellent blog! I had a quick question that I’d
like to ask if you don’t mind. I was curious to find out how you
center yourself and clear your thoughts before writing.
I have had trouble clearing my thoughts in getting my thoughts out.
I do enjoy writing however it just seems like the first
10 to 15 minutes are usually wasted just trying
to figure out how to begin. Any suggestions or tips?
Appreciate it!
Thanks a lot for the blog post.Thanks Again. Cool.
Im thankful for the post.Really thank you! Really Great.
Say, you got a nice article.Really looking forward to read more. Fantastic.
Hey, thanks for the post.Thanks Again. Cool.
wow, awesome blog article.Much thanks again. Cool.
Im grateful for the post.Much thanks again. Awesome.
After going over a few of the blog articles on your
web page, I really like your technique of writing a blog.
I book marked it to my bookmark website list and will be checking
back soon. Please check out my website as well and let me know what you think.
I really enjoy the article.Much thanks again. Cool.
Thanks for sharing, this is a fantastic blog article.Thanks Again. Awesome.
Great, thanks for sharing this article post.Thanks Again. Awesome.
I think this is a real great blog article. Really Great.
Im grateful for the post.Thanks Again. Great.
Thanks-a-mundo for the blog article.Much thanks again. Cool.
Thanks again for the article.Really thank you! Fantastic.
A round of applause for your blog.Much thanks again. Cool.
I am so grateful for your blog. Want more.
Why visitors still make use of to read news papers when in this technological world
all is available on net?
Enjoyed every bit of your article.Thanks Again. Much obliged.
A round of applause for your blog post. Awesome.
A round of applause for your article. Great.
I really like your writing style, wonderful info, appreciate it for posting :D. “If a cluttered desk is the sign of a cluttered mind, what is the significance of a clean desk” by Laurence J. Peter.
Major thanks for the blog.Really thank you! Great.
Looking forward to reading more. Great article post.Thanks Again. Great.
Great, thanks for sharing this article post.Really looking forward to read more. Will read on…
I am so grateful for your blog article. Fantastic.
Very informative blog article. Want more.
Major thanks for the blog.Really thank you!
I value the blog.Much thanks again. Fantastic.
Wow, great blog.Really thank you! Fantastic.
Thanks for the article. Cool.
I appreciate you sharing this article. Want more.
Thanks-a-mundo for the article.Much thanks again. Fantastic.
I appreciate you sharing this blog.Really looking forward to read more. Really Cool.
Very informative article.Really looking forward to read more. Keep writing.
Im thankful for the article. Really Cool.
Im grateful for the blog article.Thanks Again. Really Cool.
Hey, thanks for the article.Really looking forward to read more. Will read on…
Awesome blog post.Thanks Again. Much obliged.
I value the article. Want more.
Very neat blog.Really thank you! Cool.
Fantastic blog article.Much thanks again. Want more.
Thanks-a-mundo for the article post.Thanks Again. Fantastic.
Wow, great post.Really looking forward to read more. Really Great.
Thank you ever so for you blog post. Want more.
Im grateful for the blog.Really thank you! Fantastic.
I really enjoy the article post.Really thank you! Fantastic.
I truly appreciate this blog article.Really thank you! Much obliged.
Awesome article.Really thank you! Really Cool.
Really appreciate you sharing this blog.
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 reply as I’m looking to design my
own blog and would like to find out where u got this
from. cheers
Very nice article, totally what I wanted to find.
I am so grateful for your article.Really looking forward to read more. Really Great.
Muchos Gracias for your article.Thanks Again. Keep writing.
I appreciate you sharing this blog post.Much thanks again. Want more.
Wow that was strange. I just wrote an incredibly long comment but after I clicked
submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Regardless,
just wanted to say wonderful blog!
Very nice article, totally what I wanted to find.
Hey would you mind stating which blog platform you’re using?
I’m looking to start my own blog in the near future
but I’m having a difficult time choosing between BlogEngine/Wordpress/B2evolution and
Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something unique.
P.S My apologies for getting off-topic but I had to ask!
Enjoyed every bit of your blog post. Cool.
Really informative blog.Really looking forward to read more. Want more.
Wow, great blog article.Really thank you! Keep writing.
Im thankful for the blog article.Thanks Again. Awesome.
Hi to all, since I am really keen of reading
this website’s post to be updated on a regular basis.
It consists of good data.
I loved your article.Thanks Again. Will read on…
Really informative blog article.Really thank you! Great.
I value the post.
Appreciate you sharing, great blog.Really looking forward to read more. Fantastic.
Enjoyed every bit of your article post.Really looking forward to read more. Much obliged.
Major thanks for the article post.Really looking forward to read more. Fantastic.
Muchos Gracias for your article.Really looking forward to read more. Cool.
Very informative blog post.Much thanks again. Want more.
Great, thanks for sharing this blog article.Really thank you! Will read on…
I cannot thank you enough for the blog article.Really thank you! Cool.
Really appreciate you sharing this blog.Much thanks again. Keep writing.
Im obliged for the article post.Really looking forward to read more. Keep writing.
Say, you got a nice article post.Thanks Again. Cool.
My partner and I stumbled over here different web address and thought I might check things out.
I like what I see so i am just following you. Look forward
to looking over your web page for a second time.
I really like and appreciate your blog.Much thanks again. Much obliged.
This is one awesome article.Really looking forward to read more.
Great, thanks for sharing this post.Thanks Again.
Outstanding quest there. What happened after? Thanks!
Muchos Gracias for your article post.Really looking forward to read more. Keep writing.
Really informative article.Thanks Again. Cool.
Thank you for another great article. Where else could anybody get that type of info in such a perfect approach of writing? I’ve a presentation next week, and I am on the look for such information.
Very neat blog post.Really looking forward to read more.
Really appreciate you sharing this blog article.Thanks Again. Want more.
I think this is a real great article post.Much thanks again. Will read on…
Really informative blog article.Thanks Again. Great.
Thanks for the article post.Really looking forward to read more. Keep writing.
Fantastic article post.Really thank you! Great.
Thanks for sharing, this is a fantastic article. Awesome.
Great blog article.Really looking forward to read more. Great.
Thank you a lot for sharing this with all people you really know what you’re talking about!
Bookmarked. Kindly additionally seek advice from my site =).
We can have a link alternate contract among us
I think this is a real great blog article. Want more.
Im grateful for the article.Thanks Again. Keep writing.
These kind of post are always inspiring and I prefer to read quality content so I happy to find many good point here in the post
Thanks again for the article.Really thank you! Much obliged.
Great, thanks for sharing this post.Really thank you! Cool.
Very good blog.Really thank you!
Great, thanks for sharing this blog.Really looking forward to read more. Much obliged.
I really enjoy the blog article.Really thank you! Want more.
I am so grateful for your post. Much obliged.
Fantastic blog article.Much thanks again. Cool.
This is one awesome blog article.Much thanks again. Really Great.
Say, you got a nice blog. Cool.
Great article.Really looking forward to read more. Much obliged.
I really enjoy the post.Really looking forward to read more. Will read on…
Very informative blog.Really thank you! Really Great.
A big thank you for your blog.Really looking forward to read more. Really Cool.
Thanks so much for the article post.Really looking forward to read more. Great.
Greate pieces. Keep writing such kind of info on your page.
Im really impressed by your site.
Hi there, You have performed an excellent job. I’ll definitely digg it and in my
view recommend to my friends. I’m confident they’ll be benefited
from this website.
Im thankful for the blog article.Thanks Again. Will read on…
I value the blog article.Thanks Again. Will read on…
I think this is a real great post.Much thanks again. Want more.
Appreciate you sharing, great article.Really thank you!
Really informative article.Much thanks again. Great.
Awesome blog post.Much thanks again. Really Cool.
Very good blog article.Much thanks again. Keep writing.
Great, thanks for sharing this blog article.Really looking forward to read more. Really Cool.
Really appreciate you sharing this blog.Really looking forward to read more. Cool.
I value the article.Really looking forward to read more. Really Cool.
I really liked your blog post.Really thank you! Great.
Hey, thanks for the article.Really looking forward to read more. Awesome.
I think this is a real great blog post.Really thank you! Keep writing.
Fantastic article.Really thank you! Cool.
Looking forward to reading more. Great blog post. Much obliged.
Hey there! I just wanted to ask if you ever have any trouble with hackers?
My last blog (wordpress) was hacked and I ended
up losing several weeks of hard work due to no back up. Do you have any methods to stop hackers?
Thanks a lot for the blog.Really thank you! Awesome.
Hey, thanks for the article post. Awesome.
Thanks a lot for the post.Thanks Again. Awesome.
Very informative article post.Really looking forward to read more. Really Cool.
I think this is a real great blog.Really looking forward to read more. Cool.
Very neat blog post.Really looking forward to read more. Will read on…
I think this is a real great article.Really thank you! Fantastic.
Thanks-a-mundo for the article. Keep writing.
Thanks-a-mundo for the blog.Much thanks again. Want more.
A round of applause for your blog.Really looking forward to read more. Awesome.
just beneath, are many absolutely not related web pages to ours, even so, they’re surely worth going over
I value the blog article.Thanks Again.
Pretty nice post. I just stumbled upon your weblog and wanted to say that I have reallyenjoyed surfing around your blog posts. In any caseI will be subscribing to your rss feed and Ihope you write again very soon!
pay per click programs are really great, i could earn some decent cash from it-
[url=https://amoxicillin24.com/]amoxicillin 250mg[/url] [url=https://levitra100.com/]levitra generic[/url] [url=https://suhagra911.com/]suhagra 100[/url] [url=https://xenical365.com/]xenical otc australia[/url] [url=https://dapoxetine911.com/]dapoxetine buy online india[/url] [url=https://sildenafil48.com/]sildenafil prescription[/url] [url=https://tretinoin2019.com/]tretinoin prescription[/url] [url=https://metformin100.com/]metformin generic[/url] [url=https://synthroid100.com/]synthroid 100[/url] [url=https://azithromycin24.com/]azithromycin 250mg[/url]
I really liked your post.Really looking forward to read more. Really Cool.
I really enjoy the blog post.Thanks Again. Want more.
wow, awesome post.Really thank you! Great.
I really enjoy the article.Really thank you! Awesome.
I am so grateful for your blog post.Really thank you! Awesome.
A big thank you for your article post.Thanks Again. Awesome.
Thanks for the article post. Really Cool.
Really enjoyed this blog.Much thanks again. Really Great.
Wow, great article.Really looking forward to read more. Cool.
Im thankful for the blog post.Really thank you! Keep writing.
I think this is a real great blog.Thanks Again. Keep writing.
Very neat article.Really looking forward to read more. Really Cool.
Wow, great article.Really thank you! Fantastic.
Fantastic article.Really thank you! Will read on…
Wow, great blog post.Really looking forward to read more. Want more.
Thank you ever so for you blog article.Really thank you! Want more.
Hi there, yeah this post is really good and I have learned lot of things from it concerning blogging. thanks.|
It’s impressive that you are getting thoughts from this article as well as from our dialogue made here.|
Thank you for your post.Much thanks again.
This is one awesome post.Really thank you! Really Cool.
I know this if off topic but I’m looking into starting my own blog and was curious what all is required to get set up? I’m assuming having a blog like yours would cost a pretty penny? I’m not very internet savvy so I’m not 100 positive. Any suggestions or advice would be greatly appreciated. Thanks|
Thanks for the article post.Thanks Again. Really Cool.
I loved your blog.Really looking forward to read more. Great.
whoah this blog is fantastic i like reading your posts. Stay up the good work! You recognize, lots of people are looking around for this info, you could help them greatly. |
I think this is a real great blog post.Really thank you! Awesome.
Very neat blog article.Really thank you! Will read on…
Wow, this paragraph is fastidious, my younger sister is analyzing these things, so I am going to let know her.|
First off I want to say wonderful blog! I had a quick question in which I’d like to ask if you don’t mind. I was curious to find out how you center yourself and clear your head before writing. I’ve had a hard time clearing my mind in getting my thoughts out. I do take pleasure in writing but it just seems like the first 10 to 15 minutes tend to be wasted just trying to figure out how to begin. Any suggestions or hints? Cheers!|
Im grateful for the blog post.Really looking forward to read more. Want more.
Thanks for the article post. Really Cool.
Thank you for your blog.Really thank you! Great.
I really enjoy the blog post.Really thank you!
We’re a group of volunteers and opening a new scheme in our community. Your website provided us with valuable info to work on. You’ve done an impressive job and our whole community will be thankful to you.|
I really enjoy the blog post. Keep writing.
Awesome blog article.Much thanks again. Want more.
You’ve made some really good points there. I checked on the net for additional information about the issue and found most individuals will go along with your views on this web site.|
I loved your blog.Really thank you! Awesome.
Awesome blog.Thanks Again. Great.
i recommend what is is 11bf best online is at
No matter if some one searches for his essential thing, so he/she needs to be available that in detail, thus that thing is maintained over here.|
I really enjoy the blog article.Really looking forward to read more. Want more.
Thanks for sharing, this is a fantastic blog post.Much thanks again. Great.
Thank you for your post.Much thanks again. Will read on…
What’s up, the whole thing is going fine here and ofcourse every one is sharing information, that’s in fact good, keep up writing.|
Ridiculous story there. What happened after? Take care!|
Excellent beat ! I would like to apprentice while you amend your web site, how can i subscribe for a blog site? The account helped me a acceptable deal. I had been a little bit acquainted of this your broadcast offered bright clear idea
Keep on working, great job!|
Looking forward to reading more. Great article.Much thanks again. Really Great.
I really like it when individuals get together and share views. Great site, keep it up!|
Thanks a lot for the article.Really thank you! Want more.
A big thank you for your article post.Much thanks again. Want more.
Really enjoyed this article post.Really thank you! Cool.
Very informative article post.Much thanks again. Want more.
Im obliged for the blog article. Cool.
I could not resist commenting. Very well written!|
Thank you ever so for you blog article.Thanks Again. Will read on…
Thanks for sharing, this is a fantastic blog.Much thanks again. Really Great.
What’s up, its fastidious paragraph about media print, we all understand media is a impressive source of data.|
I want to to thank you for this very good read!! I certainly loved every bit of it. I’ve got you book-marked to check out new things you post…|
Thanks for sharing, this is a fantastic blog article.Really looking forward to read more. Will read on…
Very neat blog article.Thanks Again. Really Cool.
Interesting 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|
This is the perfect site for anyone who wishes to understand this topic. You realize so much its almost hard to argue with you (not that I really would want to…HaHa). You certainly put a new spin on a topic which has been discussed for many years. Great stuff, just great!|
Hi there, You have performed a great job. I’ll certainly digg it and in my opinion suggest to my friends. I am confident they will be benefited from this site.|