随机的艺术

随机的艺术

引子

随机,万恶之源。你做的题的数据多半是随机造的,也有能被随机乱搞过去的题,有的题标程就是随机,有的题就是出题人随机想到的 idea… 不得不说,OI 和随机还真扯不开关系。现在不妨让我们一起探索其不为大多数人所知的一面。

阅读更多
[题解] [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] Something Comforting
[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Galgame

[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Galgame

定义两棵二叉树的大小关系:

  • 若它们皆为空,则相等;
  • 若它们的大小不同,则大小更小的更小;
  • 若它们的左子树不同,则左子树小的更小;
  • 否则其大小关系等价于它们右子树的大小关系。

给你一棵二叉树,问有多少二叉树比它小。

$1\le n\le 10^6$

阅读更多
Mivik 展开(大雾