[题解] [Mivik Round nurture] Look At The Sky 加强版

[题解] [Mivik Round nurture] Look At The Sky 加强版

记一张无向图的连通块集合 $f(G)$ 为这张图所有极大连通块的大小形成的任意顺序的序列,要求对所有 $k\in [0,K]$ 求:

$$ \sum_{G\in S(n)}\frac{\sum_{i=1}^{|f(G)|}{f(G)_i^k}}{\left(\sum_{i=1}^{|f(G)|}f(G)_i\right)^k} $$

$S(n)$ 为所有大小为 $n$ 的无向图形成的集合。答案对 $998244353$ 取模。

$1\le n,K\le 2\cdot 10^5$

阅读更多
[题解] [Mivik Round nurture] Look At The Sky

[题解] [Mivik Round nurture] Look At The Sky

记一张无向图的连通块集合 $f(G)$ 为这张图所有极大连通块的大小形成的任意顺序的序列,要求对所有 $k\in [0,K]$ 求:

$$ \sum_{G\in S(n)}\frac{\sum_{i=1}^{|f(G)|}{f(G)_i^k}}{\left(\sum_{i=1}^{|f(G)|}f(G)_i\right)^k} $$

$S(n)$ 为所有大小为 $n$ 的无向图形成的集合。答案对 $998244353$ 取模。

$1\le n\le 2\cdot 10^5$,$0\le K\le 5000$

阅读更多
[题解] [Mivik Round nurture] Mirror

[题解] [Mivik Round nurture] Mirror

一个无穷的地图,行列从 0 开始标号。$(i,j)$ 可以通过当且仅当 $(i\&j)=0$。同时地图中还有 $n$ 个炸弹。现在给出两个格子,保证可以通过,问从一个格子走到另一个格子至少需要走多少步,且在步数最少的情况下至少需要拆除哪些炸弹。

$1\le n\le 2\cdot 10^5$,$0\le x,y\le 10^{18}$

阅读更多
[题解] [Mivik Round nurture] Something Comforting
[题解] [Mivik Round nurture] Get Your Wish
关于 2020
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$

阅读更多