打了一套Comet OJ - Contest #5的后三道题
A修改点权好像很烦，那就考虑根号分治，小的直接改，大的维护个trie数把询问差分一下就可以做到\(O(n\sqrt{n}logn)\)
一看怎么时限1s啊自闭了
结果后来才知道原题15s
是老板数据太水让std跑得飞快
写个暴力修点权都飞快
发现时限15s后开始写写到结束之后10min才调出来
B鬼畜期望题但是感觉还是挺套路的可能是我智商太低没想出来
C一眼二分答案然后糊一个跟深度有关的dp
可以长剖优化
但是合并信息太复杂
感觉vector不好搞就自闭了
下午和晚上改题
结果B注意到第一个人是很特殊的
于是就可以考虑到
设\(f[i]\)表示有\(i\)个人，第一个人最后死的概率
设\(p\)表示每一次操作中人死掉的概率，\(q\)表示没死的概率
枚举第一个人什么时候死
\(f[i]=\sum_{j>=1} q^{j}*p*(1-q^{j})^{i-1}\)
后面拿二项式定理展开再换下求和号得到
\(=p*\sum_{k=0}^{i-1}(_k^{i-1})*\sum_{j>=1}q^{jk} \\=p*\sum_{k=0}^{i-1}(_k^{i-1})*\frac{1}{1-q^k}\)
发现是一个卷积的形式可以ntt算出来
接下来考虑算答案
第\(i\)个人最后死的概率相当于是前面的\(i-1\)个人进行了一轮后把他变成第一个算第一个人最后死的概率
设第\(i\)个人最后死的概率为\(g[i]\)
枚举第一轮前面的死了几个有
\(g[i]=\sum_{j=0}^{i-1} (_j^{i-1})*p^j*q^{i-1-j}*f[n-j]\)
发现又是卷积再来一次ntt就好了
结果C题解的想法和我差不多
多一个log用线段树维护长剖的dp很好搞了
总结：一种方法不能拘泥于一种定式，可能会有变通
加油！继续自闭
原文：https://www.cnblogs.com/deaf/p/13339033.html