[题解] [CF1434E] A Convex Game

[题解] [CF1434E] A Convex Game

给一个长为 $n$ 的单增序列 $v$,两人轮流选数,要求两人选出的数是 $v$ 的子序列且差分数组也单增,无法选的人输。求 SG 值。

$T$ 组询问。$1\le T\le 1000,1\le v_i,\sum n\le 10^5$。

阅读更多
[题解] [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}$

阅读更多
On the Expected Subword Complexity of Random Words
字符串的期望本质不同子串个数
随机的艺术

随机的艺术

引子

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

阅读更多
[题解] [Alpha1022 的无趣比赛] 光棱碎片

[题解] [Alpha1022 的无趣比赛] 光棱碎片

给定字符串 $S$,每一位额外有权值 $v_i$,求有多少对 无序的 本质相同但出现位置不同的子串(右端点分别为 $r_1,r_2$)满足 $L\le (v_{r_1}\oplus v_{r_2})+len\le R$,其中 $L$、$R$ 为给定参数。答案对 $998244353$ 取模。

$1\le |S|,v_i,L,R\le 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,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