Colythme

题目描述有一个 $n*m$ 的 $01$ 矩阵，矩阵中 $k$ 个格子的数已经确定，你需要求出有多少种方案使得矩阵每行每列的异或和均为 $1$。对 $998244353$ 取模。 数据范围 Subtask 1暴力自不必说 Subtask 2对于 $k = 0$ 的数据，如何做？ 那么我们只要空出一列（或一行或是一行一列），让其它的格子随便填，因为不管怎么样，最后空出的这一列（行）总是可以将整行（列）的异或和变为 $1$ 同理 $k <= m$ 的数据找出一个全空的列就好了 Subtask 3仿照 $Subtask 2$ 的思路，还是找出一个被限制的格子最少的列，令该列被限制的格子数为 $p$，考虑到 $k \le 10m$，故 $p \le 10$，那么对于其它列，只要关注这 $p$ 行以及它们本身列的异或和就好了 考虑使用 $DP$，设 $f_{i, j, k, state}$ 表示前 $i$ 列前 $j$ 行，目前该列的异或和为 $k$，那 $p$ 行的异或情况状压后为 $state$ 复杂度 $O (nm2^{\frac{k}{m}})$ Subtask 4因为状态数太 ...

题意将题意转化一下 有 $m = \sum\limits_{i = 1}^n w_i$ 个数，前 $n$ 个中第 $i$ 个为 $w_i − 1$ ，剩下的 $m − n$ 个数都是 $− 1$ 求对这 $m$ 个数 $m!$ 种重排的方案中，有多少种满足重排后的序列任意前缀和不为负 题解卡特兰数的另一种组合意义首先有一个引理 给定 $n$ 个 $1$ 和 $n$ 个 $- 1$，它们组成一个长度为 $2n$ 的序列 $a$，则必定存在一个 $i$ 使得序列 $a_{i + 1…2n} + a_{1…i}$ 满足任意前缀都不小于零 证明也很简单，找到一个使得前缀和最小的位置 $i$，设 $s_{i,j}$ 表示 $a$ 上 $a_i$ 到 $a_j$ 的和，那么显然 $s_{i + 1, 2n} \ge 0$，对 $\forall k \in [1, i]$，$s_{i + 1, 2n} + s_{1, k} \ge 0$ 那么接下来求解 $n$ 个 $1$ 和 $n$ 个 $- 1$ 组成的合法序列（即任意前缀和不小于零）的方案数，也就是卡特兰数 $1$ 的编号为 $1 \sim ...

一道其实很简单然而我还是瞄了题解的题 首先考虑二分答案 显然将小于 $mid$ 的赋为 $-1$，将大于等于 $mid$ 赋为 $1$ 那么显然 $total = $ $[q_1, q_2]$ 最长后缀 $+$ 中间必选 $+$ $[q_3, q_4]$ 最长前缀 然后若 $total \ge 0$ 则 $check (mid)$ 返回 $true$ 很好然后我就不会处理了 于是题解就说将每个 $mid$ 建一棵线段树，然后用主席树就不会 $MLE$（好吧原来本来是想建序列上的主席树的说当然并不可行 那么每次 $check$ 就在 $mid$ 号版本上的树查询即可 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061 ...

题意求 $\sum\limits_{i = 1}^N \sum\limits_{j = 1}^M lcm (i, j)$ Solution易知，原式$$\sum\limits_{i = 1}^N \sum\limits_{j = 1}^M \frac{ij}{\gcd (i, j)}$$枚举 $\gcd (i, j)$ ，且将 $d$ 提出来得$$\sum\limits_{d = 1}^{\min (N, M)} d \sum\limits_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor} \sum\limits_{j = 1}^{\left\lfloor\frac{M}{d}\right\rfloor} ij[(i, j) = 1]$$将公式 $\sum\limits_{k | n} \mu(k) = [n = 1]$ 代入，得$$\sum\limits_{d = 1}^{\min (N, M)} d \sum\limits_{i = 1}^{\left\lfloor\frac{N}{d}\right\rfloor} \sum\limits ...

题意给定 $n$ 行 $m$ 列的 $01$ 矩阵，求满足 $\big(\sum_{\forall i \in A, j \in B} value_{i, j}\big) \equiv 0 \pmod{2}$ 的二元组的数量 题解首先考虑 $n = 1$，令 $1$ 的个数为 $t$，可以发现答案$$\sum\limits_{k = 0}^{\lfloor\frac{m}{2}\rfloor} \dbinom{t}{2k} \times 2^{m - t} - 1 = 2^{m - 1} - 1$$至于证明，可以考虑已经选好的数列 $\{a_1, a_2, …, a_n\}$，那么现在考虑加入第 $n +1$ 个，显然加入 $0, 1$ 都是多了两种选择 那么现在考虑将行合并成一列 但是问题是如果需要枚举选的行还是需要 $2^n$ 的复杂度，然后我考场上就想到这就凉了 那么显然每次选好了行，再选列的时候这若干个列会贯穿所有行，那就可以将每行看作一个数，并且将它们合并（异或）起来，这样就变成做 $n = 1$ 的情况了 接下来只要考虑有几种情况会使得其异或和为 $1$ （或不为 $1$） ...

prufer序列prufer序列是一种无根树的序列表示方法，一个节点个数为 $n$ 的无根树对应着唯一一种长度为 $n - 2$ 的prufer序列 无根树化prufer序列每次取编号最小的叶子节点，将其指向的“父亲”（就是它唯一指向的）节点加入prufer序列中，最终剩余两个连接的节点结束 prufer序列化无根树对于prufer序列 $A= \{a_1, a_2, a_3, …\}$，每次取最前面的元素 $a_s$，在总点集中找到最小的没有在 $A$ 中的节点 $t$，将 $a_s, t$ 连边并删去 $a_s$，可以使用 $set$ 等维护 相关定理 $n$ 个点的有标号完全图无根树计数：$n^{n - 2}$ $n$ 个点，每个点的度数为 $\{d_1, d_2, d_3, …\}$ 的有标号无根树计数：$\frac{(n - 2)!}{d_1!d_2!d_3!…}$（实际上就是一个多重集的排列数） $n$ 个点的prufer序列中第 $i$ 个点恰好出现 $d_i - 1$ 次 $n$ 个点度数为 $\{d_1, d_2, …, d_k\}$，剩余 $k + 1 \thic ...

前置知识Matrix-Tree定理对于无向图 $G$，定义其度数矩阵 $D$$$\left[\begin{matrix}deg_1 & 0 & 0 & \cdots & 0 \\0 & deg_2 & 0 & \cdots & 0 \\0 & 0 & deg_3 & \cdots & 0 \\\vdots & \vdots & \vdots & \ddots & \vdots \\0 & 0 & 0 & 0 & deg_n\end{matrix}\right]$$定义其邻接矩阵 $C$$$\left[\begin{matrix}0 & a_{1,2} & a_{1,3} & \cdots & a_{1,n} \\a_{2,1} & 0 & a_{2,3} & \cdots & a_{2,n} \\\vdots & \vdots & \vdots &a ...

看题解里有人说这题实在太水 但我连第一步对点分类都不会（虽然分类完后的确不会很难） 我依旧是太菜 好了进入正题 线段树上打 $\text{tag}$，因为它一直复制来复制去，不可能在没棵线段树上都进行修改，就考虑点的共同性质，相同性质的点可以一起修改，那么此时相当于只进行一次 $\text{modify}$ 就行了 可以将点分成五类： 一类点：半覆盖（就是修改时会经过但是不打标记） 二类点：全覆盖，打标记（区间被修改区间完全覆盖，会被访问到，被打标记） 三类点：全覆盖，不打标记（区间被修改区间完全覆盖，但不会被访问到，就是打标记全覆盖节点的子节点，不被打标记） 四类点：访问不到，会被下传标记 五类点：访问不到，不会被下传标记 那么此时方案数转概率，令 $f_u$ 表示节点 $u$ 有被打标记的概率，即 $u$ 有被打标记的线段树占比，那么最终被打标记的节点 $u$ 个数即为 $f_u \times 2^n$（其中 $n$ 表示被修改次数） 但是会发现写四类点的时候还需要知道它祖先有没有被打标记，所以还需要设一个 $g_u$ 表示节点 $u$ 及其祖先被打标记的概率，开始转移 对一类 ...

（貌似整个代码不能用 $makeroot$ ？是因为是有根树？） 因为是区间操作，所以可以考虑在区间内与区间外的差异 对于操作 $1$ ，可以看作一个生成节点包含了到下一个 $1$ 操作之间长出的节点，那么对于一个操作 $l, r$ ，相当于是在 $l$ 处将当前生成节点及其包含的节点整个移植到它更改后的位置，到 $r + 1$ 时再移植回去，所以可以考虑将一个 $1$ 操作分解为两个操作（一个移植，一个移植回去），故可以将所有操作按端点、时间排序（以及同位置修改操作必定在查询操作前，因为可以先把树建完再查询对结果没有影响），扫描一遍即可 同时，为了方便移植，将每个生成节点看作新建的一个虚点 对于操作 $0$ ，直接在虚点下 $link$ 即可，因为就算已经建了一些对于当前操作不存在的虚点，也不会对答案造成影响 对于操作 $2$ ，无法正面在 $LCT$ 上算出两点的距离，故可考虑差分，得到 $Ans = Sum_x + Sum_y - 2 * Sum_{lca}$ ，其中实点贡献为 $1$ ，虚点贡献为 $0$ 对于求 $LCA$ ，先 $access (y)$ ，再在 $acces ...

题目描述$\text{opt} = 1$ 时，代表把一个区间 $l, r$ 内的所有数都 $\text{xor}$ 上 $v$。 $\text{opt} = 2$ 时， 查询一个区间 $[l, r]$ 内选任意个数（包括 $0$ 个）数 $\text{xor}$ 起来，这个值与 $v$ 的最大 $\text{xor}$ 和是多少。 题解几乎没写过差分，看完这题之后顿时感觉到了差分的强大 首先显然第二个操作需要维护线性基，然后 $O (\log{n})$ 求解 然后因为有 $1$ 操作，所以若是直接维护区间线性基，在计算答案时不知道 $1$ 操作中的 $v$ 在当前答案中被异或上了奇数还是偶数次，故无法求解 但是在单点修改的情景下就不会有上述问题，故现在的问题是如何将区间问题转化为单点问题 于是就需要差分，让每个 $b_{i + 1} = a_{i + 1} ~ \text{xor} ~ a_i$，那么此时 $v$ 的贡献就只作用于 $b_l$ 与 $b_{r + 1}$，可直接单点修改，然后在线段树上同时维护区间线性基，查询时只需查询 $1…l$ 的前缀和（即 $b_l$），再将之 ...