牛客挑战赛38

Source

牛客挑战赛38

牛客挑战赛38C 圆桌聚餐

请先思考后再展开

这种问题一个比较好的dp思路是,记$dp_i=长度为i的连续空位,且0和i+1上有人$,这样答案就是$dp_{n-1}+1$

$dp_{0/1/2}=0,dp_{3/4}=1,dp_{n>4}=\frac{ p(\sum_{i=2}^{n-1} 1+dp_{i-1}+dp_{n-i} )+q(\sum_{i=3}^{n-2} 1+dp_{i-1}+dp_{n-i} ) }{(n-2)p+(n-4)q}$,发现可以直接前缀和优化

1
2
3
4
5
f[3]=f[4]=g[3]=(P>0),g[4]=(P>0)*2;//debug
fo(i,5,n)
f[i]=( P*2*g[i-2]+Q*2*g[i-3] )%MOD*invm( ((i-2)*P+(i-4)*Q)%MOD )%MOD,
add(f[i],1),g[i]=mm(g[i-1]+f[i]);
write(mm(f[n-1]+1));

牛客挑战赛38D 突击检查

题意:给出每个点的度数,随机选择一棵满足该度数分布的树,求在上面选X个点,这些点的联通块的个数的期望,$n \le 2e6$

请先思考后再展开

md感觉这题是前四题里面最裸最套路的了,但这题意写的跟屎一样,而且当时已经思考了挺久C的,还是觉得真要一血肯定是优先C(事实上也确实,当时再换D不一定比他们快)
$$
E((点-边)^2)=E(点^2)+E(边^2)-2*点*E(边)=X^2-2X*E(边)+E(边^2) \\
E(边)=(n-1)*\frac{C_{n-2}^{X-2}}{C_n^X} \\
E(边^2)=E((\sum x_i)^2)=E(\sum_{i \ne j} x_ix_j)+E(边)=\sum_z P_{deg_z}^2 \frac{C_{n-3}^{X-3}}{C_n^X}+(P_{n-1}^2-\sum_z P_{deg_z}^2 )\frac{C_{n-4}^{X-4}}{C_n^X}+E(边) \\
$$
code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7db20f01.html
转载请注明出处,谢谢!