[题解] [EZEC-6] 0-1 Trie

[题解] [EZEC-6] 0-1 Trie

问所有由 $n$ 个 $1$ $m$ 个 $0$ 组成且不存在相邻 $1$ 的 $01$ 串构成的 Trie 的边数。

$T$ 组数据,$T\le2\cdot 10^6$,$1\le n,m\le 5\cdot 10^{18}$

阅读更多
[题解] [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
[题解] [P4233] 射命丸文的笔记
[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Ame 和 Gura 的奇妙探险

[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Ame 和 Gura 的奇妙探险

给定 MT19937 的 10 个参数 $N$、$M$、$A$、$U$、$S$、$B$、$T$、$C$、$L$ 和 $F$,以及 $N$ 个引擎刚被初始化后生成的随机数,要求推断出初始化 MT19937 使用的种子。

$10\le M<N\le 2\times 10^5$,$0\le A,B,C<2^{32}$,$1\le U,S,T,L\le 31$,$1\le F<2^{32}$,保证 $F$ 是奇数

阅读更多
[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Galgame

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

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

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

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

$1\le n\le 10^6$

阅读更多
[题解] [Mivik 的萌新赛 & Chino 的比赛 2020] Mivik 卷积

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

定义两个多项式的 Mivik 卷积如下:

$$ f\left(x\right)\otimes g\left(x\right)=\sum_{k=0}^{\deg f +\deg g}\max_{i\in [0,\deg f] \land j\in [0,\deg g]\land i+j=k}\left\{\left[x^i\right]f\left(x\right)+\left[x^j\right]g\left(x\right)\right\} x^k $$

给出一个最高项次数为 $n$ 的多项式 $f$,试构造多个一次函数使其 Mivik 卷积为 $f$,或者指明无解。

$1\le n\le 5\cdot 10^5$,$-10^8\le f_i\le 10^8$

阅读更多