10.31闲话

发布时间 2023-10-31 21:38:42作者: crimson000

为什么都说我闲话魔怔啊???

上午下午摆了,写了写 CF。期间还被 sbf D 说不放 Atcoder 的题?,我之前写小日子的题的时候怎么不跟我说???,还说把我写的所有 agc 题解都看了一遍???。究极大卷王!

晚上劲爆你画我草,期间二多龙好像也来了?,不过在外网画那些东西小心被封???。

精选

答案还是放最后???

中午 sbf 学长建议今天闲话里面放波奇酱的本子来威胁 haosen
我:看我闲话的还有初中的不怕带坏他们吗
sbf:就光 qjy 玩过的 galgame 就都比你吃过的枣多(当时我正在吃枣)

挺难绷的。

但是出于我没看过孤独摇滚我也找不到本子我也不太想看本子的原因,还是没放???

下午见到了 haosen 家暴一幕???

haosen 方辩解:

建议以后发给 haosen 的 npy 来促进关系(无论是现在还是未来)???

解锁 crimson000 新特性:听到“小npy”脸就会迅速开始红,而且红的速度不是一般的快???。怎么会是呢???

晚上你画我猜 lbx 直接把 ytq 第一轮给举报了这一轮直接跳过???,然后就开始了小两口拌嘴模式???,也都以平常心对待了?,毕竟小两口床头吵架床尾合的??。

为什么有人说我的闲话魔怔啊?,我感觉语言也没魔怔到哪去???,不过就是一句话加个 emoji 而已???,为什么我感觉一点也不抽象,顶多也就昨天的事情有点抽象而已???,怎么会是呢

今天开始脸滚键盘了???,详情见这里

大 D MLE 晚上锐评:太卷了,受不了了。

幻想中成为大 D???。sbf 学长还是倪润东老乡???,更逆天的是苑苑也是倪润东老乡???


推歌:IMPACT -USAO

impact!


CF1097G

我们看到 \(k\) 次方可以直接上斯特林数。因此我们要求的东西就是:

\[\begin{aligned} \sum_{S}f(S)^k&=\sum_S \sum_{i=0}^{k}{k\brace i}i!\dbinom{f(S)}{i}\\ &=\sum_{i=0}^k{k\brace i} i!\sum_{S}\dbinom{f(S)}{i} \end{aligned} \]

也就是 \(\sum_S \dbinom{f(S)}{i}\)。我们进行一个组合意义,也就是在虚树内再选出 \(i\) 条边的方案数。我们就可以进行一个树形 dp。我们设 \(dp_{u, i}\)\(u\) 子树内选 \(i\) 条边的方案数,转移就进行一个树上背包,注意考虑 \(u\to v\) 这条边是否被选即可。

时间复杂度 \(O(nk+k^2)\)


你画我猜:秃鹫、胡子