Colythme

对于 $n$ 个点组成的环大小为 $m$ 的基环树个数的问题，目前已知三种解法 解法一「动态规划」在环上每个点下面搭树的方案数，相当于是在完全图中制造生成树，然后提一个点（即环上那个点）为根，故可用 $n^{n - 2}$ 来计算 然后就可以很容易想到一种背包解法，把环随便找个地方断一下，把它看成序列，即可令 $f_{i, j}$ 表示环序列前 $i$ 个点，已经使用了 $j$ 个点做环下的树的方案数，显然$$f_{i, j} = \sum\limits_{k = 0}^j f_{i - 1, j - k} \times \dbinom{n - m - (j - k)}{k} \cdot (k + 1)^{k - 1}$$然后答案要对环进行圆排列，即 $ans = f_{m, n - m} \times \frac{A_n^m}{2m}$ 复杂度 $O (n^3)$ 当然这样复杂度比较高，可以考虑将已经拼好的连通块和已经拼好的一棵树连接起来，令 $f_n$ 表示 $n$ 个点的答案 当然，为了保证不会算重，需要有一个特征点，即保证点 $1$ 不会在环上，即$$f_n = \frac{n ...

概念引入阶对于$p \in N_+$且$(a, p) = 1$，满足$a^r \equiv 1 (mod p)$的最小的非负$r$为$a$模$p$意义下的阶，记作$\delta_p(a)$ 原根定义：若$p \in N_+$且$a \in N$，若$\delta_p(a) = \phi(p)$，则称$a$为模$p$的一个原根相关定理： 若一个数$m$拥有原根，那么它必定为$2, 4, p^t, 2p^t (p$为奇质数$)$的其中一个 每个数$p$都有$\phi(\phi(p))$个原根 　　证明：若$p \in N_+$且$(a, p) = 1$，正整数$r$满足$a^r \equiv 1 (mod p)$，那么$\delta(p) | r$，由此推广，可知$\delta(p) | \phi(p)$，所以$p$的原根个数即为$p$之前与$\phi(p)$互质的数，即$\phi(p)$故定理成立 　　　　　　- 若$g$是$m$的一个原根，则$g, g^1, g^2, …, g^{\phi(m)} (mod p)$两两不同 　　　　原根求法： ...

题目描述$01$ 背包，数据范围 $1 \le n \le 1e06, 1 \le weight_i \le 300$ 题解神仙 $01$ 背包 考虑重量较小，故可以考虑根据重量分层处理 令 $f_{i, j}$ 表示使用前 $i$ 个重量，总共花费 $j$ 容量的最大价值 容易注意到在同一重量中显然要优先选择价值大的，故将每种重量按价值排序，令 $sumv_{i, j}$ 表示重量为 $i$ 的前 $j$ 大的价值前缀和，则有$$f_{i, j} = \max\limits_k \{f_{i - 1, j - ki} + sumv_{i, k}\}$$然后（通过看题解）可以发现，因为是 $j - ki$，故可以考虑按照 $j \mod i$ 分类处理，这样是满足决策单调性的 至于证明，为了方便可以将式子简化成 $f_i = \max \{f_j +sumv_{i - j}\}$ 的形式，然后用反证法或是四边形不等式都容易证明 那么最后就可以用决策单调性的套路代码或者是用分治解决了 分治比较简单，大概就是看在处理区间 $[u, v]$， $[l, r]$ 决策区间内对于 $mid$ 位 ...

概念引入　　- 点值表示　　　　对于一个$n - 1$次多项式$A(x)$，可以通过确定$n$个点与值（即$x$和$y$）来表示这唯一的$A(x)$ 　　- 复数　　　　对于一元二次方程　　　　$$x^2 + 1 = 0$$　　　　在实数范围内无解，那么我们将实数范围扩充，就得到了复数，再令$i$为该方程的解，即　　　　$$i^2 = - 1$$　　　　那么就定义$z = a + bi$的数为复数，则有　　　　当$b = 0$时，$z$为实数　　　　当$b \neq 0$时，$z$为虚数　　　　当$a = 0 \&\& b \neq 0$时，$z$为纯虚数　　　　其中，复数满足加法交换律、结合律、乘法分配率等 　　　　复数相乘：$z_1 = a_1 + b_1i, z_2 = a_2 + b_2i$，则$z_1 × z_2 = (a_1 + b_1i)(a_2 + b_2i) = (a_1a_2 - b_1b_2) + (a_1b_2 + b_1a_2)i$，它们相乘还是一个复数，在复平面上理解，就是模长相乘，幅角相加 　　　　共轭复数：当两个复数实部相同，虚部为 ...

Solution Ⅰ一道有点有趣的树形 $dp$ + 容斥，反正绕了我半天，这么神仙我也不可能写出来 首先考虑基本思路，直接求解恰好 $k$ 个较难，故考虑先求解大于等于 $k$ 的相似度的方案数，然后再容斥 考虑选定了必选的若干条边后计算方案数。显然此时整个图被分成了若干连通块，假设有 $k$ 个连通块，将连通块缩点，考虑它们可以组成的树的方案数，本来应该是 $k^{k - 2}$，然而对于每个连通块的缩点，它可以向其它连通块中包含的任意一点连接，也就是说，在 purfer 序列中，应当考虑连通块内的点编号在序列中的出现情况，而不是仅仅考虑连通块编号出现在序列中，故 prufer 序列中的每个位置可以填 $n$ 个数，即 $n^{k - 2}$，然而考虑了父亲，还需要考虑儿子，作为叶子节点的缩点后的连通块，同样的里面也是任意点向外连边，故还需乘上 $\prod size_i$，其中，$size_i$ 为连通块 $i$ 的大小，那么综上，对于一个存在 $k$ 个连通块的图，其构造的生成树的方案数为 $n^{k - 2} \times \prod size_i$ 那么现在考虑求解 $\p ...

第一次做到这种类似代数方法运用期望性质的题的说 期望性质： 对于两个独立的对象 $A, B$，则有 $E (AB) = E(A)E(B)​$ 线性性：对于对象 $X, Y​$，存在 $E(aX + bY) = aE(x) + bE(Y)​$ 首先设计函数 $I_i(x) = \begin{cases} 1 x_i \neq x_{i - 1} \ 0 x_i = x_{i - 1} \end{cases} (i > 1), ~ I_1(x) = 1​$，则有 $B(x) = \sum\limits_{i = 1}^n I_i(x)​$，故$$\begin{aligned}E (B^2(x)) &= E (\sum\limits_{i = 1}^n I_i(x)\sum\limits_{j = 1}^n I_j(x)) \\&= E (\sum\limits_{i = 1}^n\sum\limits_{j = 1}^n I_i(x)I_j(x)) \\&= \sum\limits_{i = 1}^n\sum\limits_{j = 1}^ ...

题意现在给定你n个字符串，询问每个字符串有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串（注意包括本身）。 题解首先是广义后缀自动机，就是每次将$last$归为$Root$，从而将几个后缀自动机拼在一起处理 那么现在需要知道每个字串在$n$个母串中的出现次数，所谓字串，就是所有前缀的所有后缀，所以可以顺着前缀走，那么通过$Parent$树找后缀，一直往上跳，那么需要加一的所有后缀就是所属母串并非当前母串的那几个 此时再整理出每个所属母串个数$Size >= K$的初始贡献，即$Len[i] - Len[Father[i]]$，反之赋$0$ 又子串为前缀的后缀，那么一个节点的贡献即为它祖先至它本身的贡献前缀和，即它所有后缀能够构成的子串数 最后再遍历一遍前缀统计答案即可 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879 ...

题意每个点有各自的权值，要求维护操作：动态加边、动态修改权值、询问在每个点只能经过一次的情况下两点间路程中的最大权值和 题解首先对于一个静态的图，将其缩点，可以得到一棵树，那么两点间询问的答案即为它们之间经过的 $BCC$ 的权值和 支持动态加边，就需要用到 $LCT$ 去维护 $BCC$ 如果两个点所在 $BCC$ 在不同树上，那么直接连边即可；反之，则说明形成了环，就暴力将这条链拖出来，用选定一个标准节点，用并查集将链上其它节点连到标准节点上，容易证明，这样的复杂度是均摊 $O (\log n)$ 的 查询即修改容易实现，不加赘述 注意，此题没有删边，所以 $findroot$ 可用另一个并查集代替，不然会 $T$ 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969 ...

D - Anticube说实话质因数分解的题都挺有意思的 首先对于每个数，显然里面存在的质数三次方的因子都是无贡献的，那么将其的每个质因数化简，即对于质因子 $p^k$，将其变为 $p^{k ~ mod ~ 3}$ 那么两个数若乘积为完全立方数，则必须满足它们的每一个相同质因子都是“互补的”（即次数相加为 $0$ 或 $3$），同时显然一定不存在大于一个 $> \sqrt[3]n$ 的质因数 $p$，那么解法就很显然了 就是筛出 $[2, \sqrt[3]n]$ 的质数，然后对每一个数进行化简，然后将化简后的数的计数器加一，最后在所有两两“互补”的数中取 $max$ 求和即可 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 ...

D - Stamp Rally整体二分 + 并查集常规操作 不过记得每次仅将当前递归时使用的并查集删去即可，之前的保留，所以对于那些被忽略的答案的位置，也需要递归到然后加入并查集 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154#include <iostream>#include <cstdio>#include ...