首页 > 其他分享 >CF248E Piglet's Birthday

CF248E Piglet's Birthday

时间:2023-10-27 18:12:39浏览次数:32  
标签:Piglet 蜜罐 CF248E Birthday 考虑 dbinom

提前了一个月,就做掉了这题,不过还是庆祝一下吧。(

考虑 dp。令 \(f_{u,i}\) 表示货架 \(u\) 还剩 \(i\) 罐未被吃的蜂蜜的概率。答案就是 \(\sum f_{u,0}\)。

考虑一次修改 \(u\to v\),由于被移动的蜜罐都被吃了,所以 \(v\) 的 \(f\) 数组不变,只需要考虑 \(f_u\) 的变化。

枚举吃掉了 \(j\) 个有蜜的蜜罐:

\[f_{u,i}\cdot\frac{\dbinom{i}{j}\dbinom{a_u-i}{k-j}}{\dbinom{a_u}{k}}\to f_{u,i-j} \]

然后就做完了,复杂度 \(O(qk^2A)\)。

标签:Piglet,蜜罐,CF248E,Birthday,考虑,dbinom
From: https://www.cnblogs.com/Ender32k/p/17792930.html

相关文章

  • CF718E Matvey's Birthday
    不难发现答案\(\le15\),极限的情况大概就是\(aabbcc\cdotsgghh\),此时跳一步和走一步等效。这启示我们固定点\(i\),统计\(d(i,j)=D,j<i\)的\(j\)的个数,拆成\(i-j\le15\)的贡献和\(i-j>15\)的贡献。为了方便,以下称从\(i\)到\(i+1\)或\(i-1\)为「走」,在相同颜色......
  • UVa 10167 Birthday Cake (枚举)
    10167-BirthdayCakeTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=1108BackgroundLucyandLilyaretwins.Todayistheirbirthday.Motherbuysabirthd......
  • Birthday!
    AkiyamaMio:1.15TedezaRize:2.14NanamiTouko:2.19KoitoYuu:4.5HotoKokoa:4.10ShimamuraHougetsu:4.10YoshikawaYuuko:4.15SilenceSuzuka:5.1SpecialWeek:5.2KousakaReina:5.15NakagawaNatsuki:6.23Yoroizu......
  • CF590E Birthday
    \(\text{Solution}\)建出ACAM后利用fail树就可以确定子串关系了,如果建成有向图然后看问题,考虑最长反链等于最小链覆盖,那么就是求一个可重路径覆盖问题Floyd传递闭......
  • Birthday Attack
    BirthdayAttackQ&A1Q:Howmanypeoplemustbethereinaroomtomaketheprobability100%thatat-leasttwopeopleintheroomhavesamebirthday?A:367(s......
  • Codeforces Round #619 (Motarack's Birthday)
    题面DarkisgoingtoattendMotarack’sbirthday.DarkdecidedthatthegiftheisgoingtogivetoMotarackisanarrayaofnnon-negativeintegers.Darkcr......
  • NEUOJ 1207(Birthday present-前缀和)
    给你一个数组a,给你一个k,你可以讲每个数减去不超过k,要求最后的GCD最大,求这个gcd1 ≤ n ≤ 3·1e5; 1 ≤ k ≤ 1e61 ≤ ai ≤ 1e6显然min(ai)<=k时,答案为min......
  • Happy Second Birthday Jenkins X!
    始于2019年初的JenkinsX项目在去年的1月14号庆祝了它的第一个生日,这对任何开源项目来说都是一件大事,我们刚刚又庆祝了它的第二个生日。JenkinsX的两周年!JenkinsX已......
  • 双哈希_Birthday_Cake
    BirthdayCake思路:找到每个串的公共前后缀,统计公共前后缀之间的字符串的hash值,并判断所给n个串中是否存在符合条件的串eg:abbddab对于该串,我们不难发现,公共前后缀是ab,公......
  • H - Mr. Panda and Birthday Song Gym - 101775H
    题意:给你一个长度不大于1e6的字符串,由'a'-'z'或‘?’组成,且‘?’可转化为任意小写字母。和两个数x,y。现在有两个条件:字符串中存在任意一个长度为x的子串均为元音,或存在......