CVBB ACM Team 2020-2021:teams:i_dont_know_png:nikkukun

2020-2021:teams:i_dont_know_png:nikkukun:connected_component

Anonymous (anonymous@undisclosed.example.com) — 2020-05-15T02:00:51+0800

连通分量有向图：强连通分量强连通分量中的一个点属于且仅属于一个边双连通分量。缩点时，同一连通分量的点缩成一个点，最终会变成一个 DAG。唯一需要注意的是，重新建图时要判断原边的两个点是否在同一个强连通分量内。$K_1,K_2$$K_1$$K_2$$2, 4$$(2, 4)$$(1, 2)$$1, 2$$K_2$

2020-2021:teams:i_dont_know_png:nikkukun:cycle_space

Anonymous (anonymous@undisclosed.example.com) — 2020-05-12T16:52:56+0800

环空间如果两个环可以异或相消，则一个图中的所有简单环，可以由某个钦定的点 $u$ 为始末点的所有简单环组合得到。实现可以用 DFS，记录第一次访问到某个点时的路径异或值 $\mathrm{dis}_u$，则每次访问到已经经过的点时，只需要把当前的异或值和 $\mathrm{dis}_u$$\mathcal{O}(V + E)$$u$$v$$u$$v$$u$$u$$u$$u$$G$$G$$G$$F$$T$$G$$T$$W_c(G)$$m - n + c$$m - n + c$$m$$n$$c$

2020-2021:teams:i_dont_know_png:nikkukun:generating-function

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T19:45:34+0800

生成函数本文主要做一个归纳性的总结。常见的生成函数形式： * 普通型生成函数（Ordinary Generating Function, OGF）：$F(x) = \sum_{i=0}^{\infty} a_i x^i$ * 指数型生成函数（Exponential Generating Function, EGF）：$F(x) = \sum_{i=0}^{\infty} \dfrac {a_i}{i!} x^i$ OGF 的卷积表示组合，而 EGF 的卷积表示排列——之前没怎么理解这个说法，现在就比较明白了。考虑卷积结果的某一项 $x^n$$F(x) = \prod_{i=1}^m F_i(x)$$F_i(x)$$n$$G(x) = \prod_{i=1}^m G_i(x)$$G_i(x)$$n$$\sum_{i = 0} ^ {\infty} a^i x^i = \dfrac 1 {1 - ax}$$x$$$ \sum _{i=0} ^{\infty} x^{ai} = \dfrac 1{1-x^a} $$$$ \sum _{i=0} ^{\infty} a^i …

2020-2021:teams:i_dont_know_png:nikkukun:isotonic_regression

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T18:11:14+0800

保序回归问题本文作为一个总结性质的东西，不涉及具体的证明，详细请参阅参考资料部分的论文。序列上的保序回归问题对给定的数列 $a_1, a_2, \ldots, a_n$，找到一个非降序列 $b_1, b_2, \ldots, b_n$，使得 $$ \text{minimize } \sum _{i=1}^n w_i |a_i - b_i|^p, \ p \in \mathbb{N}_+ $$ 其中 $p$ 是一个定值，并称其为 $L_p$$i$$\Delta x$$w_i(\Delta x)^p$$[l, r]$$\sum _{i=l}^r w_i |a_i - k|^p$$k$$L_p$$[l, r]$$b_i$$L_p$$w_i \equiv 1$$L_1$$a_l \leq a_{l+1} \geq \cdots \leq a_r$$b_i = a_i$$a_l \geq a_{l+1} \geq \cdots \geq a_r$$b_i = L_1$$L_1$$O(\log n)$$L_2$$L_2$$a_l > a_{l+1} > \cdots > a_r$$…

2020-2021:teams:i_dont_know_png:nikkukun:mobius_inversion

Anonymous (anonymous@undisclosed.example.com) — 2020-05-26T10:20:26+0800

莫比乌斯反演积性函数数论函数是一类定义域在正整数上的函数。若对数论函数 $f$，且 $\forall a, b$ 使得 $(a, b) = 1$，都满足 $$ f(ab) = f(a) \cdot f(b) $$ 则称 $f$ 是积性函数。如果条件弱一些，不需要 $(a, b) = 1$ 也有上式成立，则称 $f$ 是完全积性函数。只要 $f$$f$$p$$f(p^a)$$f$$f, g$$$ h(n) = f(n^p) \\ h(n) = f^p(n) \\ h(n) = f(n)g(n) \\ h(n) = \sum _{d \mid n} f(n) g \left(\dfrac nd \right) \\ $$$$ [P] = \begin{cases} 1, &P \text{ is true} \\ 0, &P \text{ is false} \\ \end{cases} $$$\varepsilon(n) = [n = 1]$$\mathrm{id}(n) = n$$n$$1(n) = 1$…

2020-2021:teams:i_dont_know_png:nikkukun:palindrome_series

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T18:11:01+0800

Palindrome Series 前置知识：PAM。文中可能会用到的记号如下： * $|S|$：字符串 $S$ 的长度； * $\mathrm{per}(S)$：字符串 $S$ 的周期集合； * $\mathrm{minper}(S)$：$\mathrm{per}(S)$ 的最小值。 Border Series 首先不加证明地介绍一些 border 理论的引理，以便于之后集中使用。具体证明可以参考文末提及的资料，这里仅做记录。$p, q \in \mathrm{per}(S)$$p + q \leq |S|$$\gcd(p, q) \in \mathrm{per}(S)$$p = \mathrm{minper}(S) \leq \dfrac {|S|}2$$x \in \mathrm{per}(S)$$p \mid x$$S$$\geq \dfrac {|S|}2$$S$$O(\log |S|)$$S$$< \dfrac {|S|}2$$S$$T$$T$$S$$O(\log |S|)$$O(\log |S|)$$S$…

2020-2021:teams:i_dont_know_png:nikkukun:pruefer-sequences

Anonymous (anonymous@undisclosed.example.com) — 2020-08-07T18:10:21+0800

Prufer 序列 Prufer 序列构造了一个 $n \geq 2$ 个结点的无根树，与一个长度为 $n - 2$、值域在 $[1, n]$ 的序列之间的双射。从无根树到 Prufer 序列每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n - 2$$n$$1$$1$$n$$n$$n-2$$d$$d-1$$n^{n-2}$$d_1, d_2, \ldots, d_n$$$ \dfrac {(n-2)!}{\prod_{i=1}^n (d_i - 1)!} $$$d$$d-1$

2020-2021:teams:i_dont_know_png:nikkukun:system_of_difference_constraints

Anonymous (anonymous@undisclosed.example.com) — 2020-05-14T02:35:39+0800

差分约束系统需要求解一堆形如 $x_j - x_i \leq k$ 的不等式组。不等式 $x_j - x_i \leq k$ 代表了一条从 $x_i \to x_j$ 连一条边权为 $k$ 的边，系统的一个解对应了图的一个最短路。由于整个图不一定连通，因此通常加一个超级源点 $x_0$，边权为 $0$$(x_1, x_2, \ldots, x_n)$$(x_1 + d, x_2 + d, \ldots, x_n + d)$$x_0 = 0$$x_i$$x_j - x_i \leq k$$x_j$$x_j - x_i$$k$$x_j$$x_0 = 0$$0$$1$

2020-2021:teams:i_dont_know_png:nikkukun:yukicoder-contest-260

Anonymous (anonymous@undisclosed.example.com) — 2020-08-14T16:59:24+0800

yukicoder contest 260 (Typical Game Contest) 比赛链接经典游戏场，全场玩游戏，全场不会玩。 B - シュークリームゲーム（Easy）题目描述有一个 $n \leq 10^5$ 个结点的环，每个节点上有一个数字 $a_i$。一开始，Alice 和 Bob 占领了两个不同的结点 $s, t$$a_i$$s, t$$p$$q$$p, q$$p, q$$p, q$$n \leq 10$$a_1, a_2, \ldots, a_n$$x$$\dfrac 1x$$+x$$1 - \dfrac 1x$$S$$P(S)$$S$$P(S, i, j)$$S$$i$$j$$$ P(S) = \max_{i} \min_{j} P(S, i, j) $$$j$$P(S, i, j)$$i$$P(S, i, j)$$S_1, S_2$$S$$i, j$$Q(S_1)$$S_1$$$ P(S, i, j) = \dfrac 1{a_i} Q(S_1) + \left(1 - \dfrac 1{a_i} \right) \left[\dfrac 1{a_…