RainAir
My OI Blog
RainAir

未分类
文章归档

「CF908D」New Year and Arbitrary Arrangement

题目大意 一开始序列为空。每次你有 $P_a$ 的概率往序列末尾添加一个a,有 $P_b$ 的概率往序列末尾添加一个b。当子序列ab的出现次数 $\geq K$ 时停止,问子序列ab的期望出现次数。 保证有 $P_a+P_b = 1$(显然) 题解 考虑 dp,设 $f_{i,j,k}$ 表示拿了 $i$ 个 a,$j…

   174   2019-10-09   174 去吊打作者

「CF1097G」Vladislav and a Great Legend

CF1097G 题意大概是给 $n$ 个点的树,定义 $f(S)$ 表示 $S$ 中所有的点构成的斯坦纳树的大小。求 $$\sum_{S \subseteq [1,2,\cdots,n],S \neq \emptyset} f(S)^k$$ 解:首先看到 $k$ 次方和发现不太好求,我们可以拆成斯特林数的形式: $$x^k = \sum_{i=0}^k i! (^x_i…

   357   2019-08-03   357 去吊打作者

杜教筛学习笔记

介绍 我们在 OI 题目中,不难会遇到给定一个积性函数 $f(x)$,求 $$\sum_{i=1}^N f(x)$$ 的题目。虽然对于积性函数我们已经有成熟的线性筛方法来说可以做到 $O(n)$,可是有的出题人就是毒瘤,可是有的题目的数据范围要求给出一个复杂度小于线性的做法,这时候神仙就搞…

   654   2019-03-31   654 去吊打作者

NOIP 2018 SD游记

咕了一周之后来写一片游记...... 先照例 Orz 吊打我的 Logey Day0 考前坚信不玩炉石传说,为自己奶了一口。 感觉考在正睿前刷了 $50$ 套模拟赛应该没问题吧? 坐在车上一边骂着**司机不走高速,一边低头颓着手机然后下车的时候头好晕,手机也没电了。 抽到了外校,又…

   1,320   2018-11-18   1,320 去吊打作者
标签
近期评论