动态规划

题目描述有一个 $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因为状态数太 ...

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 ...

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

首先有一个性质 对于 $n \ge 11$，操作 $1$ 必定有解 一个来自 $\text{Okami}$ 的严谨证明： 考虑互不相同的数 $x, y, z, …$，则有 123xx y x+yx y z x+y x+z y+z x+y+z 也就是对于 $n$ 个互不相同的数它们显然可以拼出 $2^n - 1$，那么根据抽屉原理，则有 $2^n - 1 \ge 1000$ 时必定有解，则命题成立 那么剩下的就直接 $\text{bitset}$ 优化背包就好了（注意可以直接背包因为若集合 $X$ 和 $Y$ 同时选了一个数，那么它们同时去除该数也是相等的），至于操作 $2$ 的影响则直接树状数组统计每个数要立方几次，由于 $\bmod V$，那么直接倍增处理即可 单词询问复杂度 $O (\frac{(r - l + 1)^2V}{32})$ 代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 ...

斯坦那树百度释义 斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。 即最小斯坦那树即为并非选择所有的结点，而是选择一部分结点，为保证它们连通，且求解最小开销 题解斯坦那树模板 发现直接表示点的存在性没有意义 设函数 $f[i][state]$ 表示：对于点 $i$，其它结点与其连通情况 那么有两种转移 其一、由其子集转移$$f[i][state] = \min\limits_{sub \in state} \{f[i][sub] + f[i][\complement_{state}sub] - value_i\}$$之所以要减去 $value_i$ 是因为会算重 附：枚举子集的方法 1for (int sub = state & (state - 1); sub; sub = (sub - 1) & state) 其二、由相邻当前状态下结点转移$$f[i][state] = \min\limits_{state_p = tru ...

首先易得方程，且经过变换有 $$\begin{aligned} f_i &= \min\limits_{dist_i - lim_i \le dist_j} \{f_j + (dist_i - dist_j)p_i + q_i\} \\ f_j &= p_idist_j + f_i - dist_ip_i - q_i \end{aligned}​$$ 在一条直线上时，斜率优化可以用普通$CDQ​$分治实现（会不会过于麻烦？），那么对于在树上斜率优化时，考虑点分治 这时就在点分治中运用$CDQ$分治的思想，即使用在当前重心管辖范围内的通向根节点的那一条链上的节点来更新其它节点就好了 注意在分治中的斜率优化时在凸包上加点和更新右侧节点答案要同时进行，不然当前最优解可能会在后面由于斜率被删去，导致答案错误，还有由于下面代码是由深度由小到大处理的，所以是反着维护下凸包，即上凸包 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354 ...

首先每次买卖一定是在某天 $k$ 以当时的最大收入买入，再到第 $i$ 天卖出，那么易得方程： $$f_i = \max \{\frac{A_iRate_kf_k}{A_kRate_k + B_k} + \frac{B_if_k}{A_kRate_k + B_k}\}$$ 再令 $$\left\{\begin{aligned} x_k = \frac{Rate_kf_k}{A_kRate_k + B_k} \\ y_k = \frac{f_k}{A_kRate_k + B_k}\end{aligned}\right.$$ 则有 $$\begin{aligned} f_i &= \max \{A_ix_k + B_iy_k\} \\ y_k &= - \frac{A_i}{B_i}x_k + \frac{f_i}{B_i} \end{aligned}$$ 那么现在需要找到一个点 $(x_k, y_k)$ 使得直线的截距最大 由于斜率和横坐标皆不满足单调性，可以用平衡树等维护，这里使用CDQ分治实现 实现过程如下： Ⅰ 将数据按照斜率$\frac{A_i}{B_i}$降序排 ...

后面发现这是某次考试的原题来着 怕是太久没打过状压然后连 $k \le 5$ 可能要状压这么明显的提示都给无视了然后就随便敲了个矩阵树骗了 $50$。。。 好所以这题是一道状压 令 $state$ 表示对于 $i$ 点（包括它本身）的前 $k$ 个点的连通状态，$e.g. \{1, 1, 2\}$ 表示 $\{1, 2\}, \{3\}$ 点分别连通 注意为了去重要用最小表示，于是即使当 $k = 5$ 时状态数也不过就 $52$ 个而已了 再令 $f_{i, j}$ 表示前 $i$ 个点且 $i$ 点连通状态为 $j$ 时的方案数，$g_{i, j}$ 表示状态 $i$ 转移到状态 $j$ 时的方案数，则有方程$$f_{i, j} = \sum_k f_{i - 1, k} * g_{k, j}$$可以发现这就是一个矩阵转移式，故直接矩阵乘法即可 那么至于计算 $g_{i, j}$ 则枚举 $i$，及当前点与前面点的连通状态 $state$（二进制表示），然后并查集维护一下，判断当前 $state$ 是否会与之前冲突（连边后无环且原状态中的最前点（即会被刷掉的点）与当前的 $k$ ...

首先普通 $DP$ 式子很好列 令 $f[i][j]$ 表示 $i$ 个小朋友分 $j$ 个糖果且每人至少一颗的答案，则有$$f[i][j] = \sum\limits_{k = 1}^j f[i - 1][j - k](Ok^2 + Sk + U)$$接下来用生成函数优化该式 令 $g[k] = Ok^2 + Sk + U$，则$$f_i(x) = f_{i - 1}(x)g(x)$$其中 $f_0(x) = 1$ 所以答案即为$$[x^M] \sum\limits_{i = 0}^A f_i(x) = [x^M] \sum\limits_{i = 0}^A (g(x))^i = [x^M] \frac{1 - (g(x))^{A + 1}}{1 - g(x)}$$ 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384 ...

挺有趣的一道 $dp$，两问实际上就相当于是第一问是第二问的部分分 第一问一开始以为要 $dp$，然而并不用 对于这种高度然后求方案数的题，可以只考虑其相对位置，因为只要所有相对位置确定了，那么整个序列就唯一确定了 首先肯定要先将它们以高度为第一关键字（由大到小），关键值为第二关键字（从小到大）排序 那么对于第 $i$ 座山，它就会有 $\min (i, key_i)$ 个相对位置可以占，因为有相同高度的山峰，所以还会多出 $same$ （$i$ 前面与其高度相同的山峰的个数）个位置 那么 $ans_1 = \prod\limits_{i = 1}^n min (i, key_i + same)$ 第二问症结还是在于相同高度的山峰会产生重复 但是显然如果一次性确定好所有相同山峰的位置是不会产生重复的，故考虑将每一组相同高度的山峰放在一起处理 为了避免重复，需要强制令这些相同高度的山峰放置有序，即后放的一定在先放的后面，那么就可以令 $f_{i, j}$ 表示（当前组相同高度山峰）前 $i$ 个放在前 $j$ 个位置上，并且第 $i$ 放在第 $j$ 个位置的方案数，则有（下示方程表示区 ...