Powerful Number

[笔记] RNG and XOR

最初 $x=0$,每一次操作以 $p_i$ 概率选择 $i$ 并将 $x$ 设为 $x\otimes i$(异或),问对于所有 $k$ ($1\le k\le 2^n$)期望操作多少次能第一次变成 $k$。

$1\le n\le 18$

阅读更多

[笔记] 黎明前的巧克力

给定 $n$ 个数 $a_i$,求把 $n$ 个数分为三个集合,且前两个集合异或值相同的方案数。集合可区分而集合内的元素不可区分。

$1\le a_i,n\le 10^6$

阅读更多

[笔记] 收集邮票

有 $n$ 种邮票,第 $i$ 轮会花费 $i$ 的代价随机得到一种,问收集完全部邮票的期望代价。

$1\le n\le 10000$

阅读更多

[笔记] 情侣?给我烧了!

一个影院有 $n$ 排座位,每一排两个座位。有 $n$ 对情侣看电影,每个人随机坐,问恰好有 $K$ 对情侣坐在同一排的方案数。

$T$ 组询问。$1\le T\le 2\cdot 10^5$,$1\le n\le 5\cdot 10^6$,$0\le K\le n$。

阅读更多

[笔记] Fibonacci 的 LCM

给 $n$ 个数 $a_i$,求 $\operatorname{lcm}(f_{a_1},f_{a_2},\cdots f_{a_n})$。$f_i$ 是 Fibonacci 数列,$f_0=0,f_1=1,f_i=f_{i-2}+f_{i-1} (i>1)$。

$1\le n,\max\{a_i\}\le 10^6$
阅读更多