线性DP

初来乍到，4h20min的题我打了2h，成功垫底，恭喜我自己 $\text{score：20 + 0 + 0 = 20 rk：26/27}$ Problen A题目描述 题解看他们都会写。。这种比较复杂的容斥我几乎都没写过。。 前置知识：高维前缀和举个例子，对比如现在要求解 $\sum\limits_{s = 0}^{2^n - 1}\sum\limits_{j \in s} a_j$（此处 $\in$ 是二进制表示下的意义），直接枚举子集是 $O (3^n)$ 的，那么高维前缀和可以优化到 $O (n2^n)$ 考虑低位前缀和，比如三位，我们是不是可以这么写 123456789101112for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) for (int k = 1; k <= n; k ++) a[i][j][k] += a[i - 1][j][k]for (int i = 1; i <= n; i ++) for (int j = 1; ...

成功由垫底转至中下水平。。 恭喜。。我？ $\text{score：55 + 0 + 0 = 55 rk：21/33}$ Problem A：猜想题目描述 数据范围对于所有测试数据，记 $l$ 表示 $n$ 的长度，则 $1 \le l \le 2 \times 10^5$，保证 $n$ 的最高位为 $1$，且除此之外的 $l - 1$ 位使用 $\text{std::mt19937}$ 随机生成 题解考场上敲了个 $55$ 分的暴力，本来想说看能不能枚举每一位然后直接算它的状态，然后不行 出题人提供的题解没看懂，就看了看其他 $A$ 掉的人的思路 首先考虑分块，使分出的块尽量大，取块大小 $L = 24$，对每一块分别处理 处理当前块时先不考虑右移删 $0$ 的情况，先只考虑乘三加一的情况，最后只要在答案上加上二进制位总数即可 设第 $i$ 块储存的数为 $a_i$ 类似线段树处理乘法时的操作，记两个变量 $mul, add$ 记录总共乘了多少，总共进位多少，那么转移到 $a_j$ 时则有 $a_j = mul * a_j + add$，以此类推 细节就看代码吧 12345678 ...

今日又是三道集训队作业原题。。又没部分分。。 反正我都不会必定爆零就没交了。。 $\text{score：NULL rk：NULL}$ Problem A：Birthday题目描述给定 $n$ 个仅包含 a,b 的字符串。 你需要去掉尽可能少的字符串，使得剩下的字符串中不存在某一个串是另一个串的子串。 数据范围对 $100\%$ 的数据，$1 \le n \le 750, ~ \sum\limits_{i = 1}^n |s_i \le 10^7$ 题解原题 CF590E 由于 $n$ 很小，很显然可以对每一对字符串判断一个是不是另一个的子串，如果是就连个单向边，最终形成一个 $DAG$ 然后在上面搞 那么对于建图，先建个$\text{AC}$自动机，在 $trie$ 的结尾存一下编号，然后把每个串扔上去匹配，每次匹配与走到节点 $fail$ 树上的所有编号（即它的子串）连边 当然直接连边肯定会 $T$，实际上你只要往在 $fail$ 树往上找到的第一个编号以及本身节点的编号（如果存在的话）连边，然后传递闭包就好了，这样复杂度就正确了 那么接下来的任务就是在 $DAG$ 上求出最长 ...

显然答案是总哈密顿回路数除以值得记录的竞赛图数 那么先求解总哈密顿回路数，考虑每个哈密顿回路会在几个值得记录的竞赛图中，则有$$Hamitons = (n - 1)!2^{C_n^2 - n}$$即总共有 $(n - 1)!$ 种哈密顿回路，然后剩下的边随便选 于是现在考虑值得记录的竞赛图数 首先如果一个竞赛图要有哈密顿回路，那么它至少要有一个包含所有节点的环，即该图是强连通的，并且显然非强连通竞赛图它一定不存在哈密顿回路，所以有结论 有且仅有强连通竞赛图存在哈密顿回路 那么问题转化为求解强连通竞赛图 发现正面难以求解，就考虑反面求解 设 $f_n$ 表示 $n$ 个节点的强连通竞赛图数，$g_n$ 表示 $n$ 个节点的竞赛图数（即 $2^{C_n^2}$），可得 $DP$ 方程$$f_n = g_n - \sum\limits_{j = 1}^{n - 1} f_jg_{n - j}\dbinom{n}{j}$$其中求解非强连通竞赛图部分是每次将拓扑序最小的强连通分量提取出来计数，那么剩下的点随意连接（注意，此时取的是拓扑序最小的强联通分量，故该强联通分量与其它连通分量的连边方 ...

后缀数组在文本串中寻找子串在文本串 $T$ 中寻找模式串 $S$，那么 $S$ 一定是 $T$ 的某个后缀的前缀，后缀排序后，在 $SA$ 中二分 $S$ 的位置，每次 $check$ 比较时间 $O (|S|)$，总时间复杂度 $O (|S| \log |T|)$ 比较两个子串的大小关系比较 $S$ 的子串 $A = S[l_1…r_1], B = S[l_2…r_2]$ 的大小关系 若 $lcp (l_1, l_2) \ge \min (|A|, |B|)$，则 $A < B \Longleftrightarrow |A| < |B|$，反之 $A < B \Longleftrightarrow rk_{l_1} < rk_{l_2}$ 本质不同子串数目设字符串 $S$ 长度为 $n$ $ans = \frac{n(n + 1)}2 - \sum\limits_{i = 2}^n height[i]$ 从字符串首或尾取字符构成最小字典序的字符串[USACO07DEC]Best Cow Line G 最基本贪心，若两端字符不同，优先取大的，那么问题就在于两端相 ...

题目描述有一个 $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 ...

首先每次买卖一定是在某天 $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}$降序排 ...

首先普通 $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$ 个位置的方案数，则有（下示方程表示区 ...