Siyuan 的博客

「2019 Multi-University Training Contest 2」Everything Is Generated In Equal Probability

题目链接：HDU 6595

Y_UME 有一个整数 $N$ 和一串有趣的代码：

首先，他先等概率随机一个正整数 $n \in [1, N]$，再等概率随机一个长度为 $n$ 的排列。最后他会将这个排列传入函数 $\text{Calculate}$ 并得到一个返回值。请你求出这个值的期望，答案对 $998244353$ 取模。

本题有多组数据。

数据范围：$1 \le N \le 3000$，$\sum N \le 5 \times 10 ^ {4}$。

「2019 Multi-University Training Contest 1」Typewriter

题目链接：HDU 6583

有一天，Jerry 发现了一个奇怪的打字机。这个打字机又 $2$ 种模式：第一种模式可以花费 $p$ 的代价在最后插入一个任意字符；第二种模式可以花费 $q$ 的代价复制任意一个子串并插在最后。

现在 Jerry 想要给 Tom 写一封信，这封信可以用一个只包含小写字母的字符串 $S$ 表示。可惜 Jerry 很穷所以他想知道写这封信的最小花费。

本题由多组数据。

数据范围：$1 \le \lvert S \rvert \le 2 \times 10 ^ {5}$，$\sum \lvert S \rvert \le 5 \times 10 ^ {6}$。

「2019 Multi-University Training Contest 1」Function

题目链接：HDU 6588（加强版 LOJ 6686）

本文为加强版题解。

给定正整数 $n$，请你求如下式子的值：

$$ \sum_{i = 1} ^ {n} \gcd(\left\lfloor\sqrt[3]{i}\right\rfloor,i) $$

答案对 $998244353$ 取模。

数据范围：$1 \le n \le 10 ^ {30}$。

「2019 Multi-University Training Contest 1」Sequence

题目链接：HDU 6589

Tom 有一个长度为 $n$ 的序列 $a$，他想要进行 $k$ 种不同的操作。

对于类型为 $k$ 的操作，他会对于所有的整数 $i \in [1, n]$ 计算出 $b_i = \sum_{j = i - kx} a_j(x \ge 0, 1 \le j \le i)$ 并将 $a_i$ 替换为 $b_i \bmod 998244353$。

他想要求出 $m$ 次操作后的序列。为了减小输出量，你只需要求出 $\bigoplus_{i = 1} ^ {n} i \cdot a_i$ 的值。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n \le 10 ^ 5$，$1 \le m \le 10 ^ 6$，$1 \le a_i \le 10 ^ 9$，$1 \le k \le 3$。

「2019 Multi-University Training Contest 1」Operation

题目链接：HDU 6579

给定一个长度为 $n$ 的序列 $a$，接下来有 $m$ 个操作，操作分为如下 $2$ 种：

• 0 l r：选择 $a_l, a_{l +1}, \dots, a_{r}$ 中的一些数，使得他们的异或和最大，输出最大的异或和。
• 1 x：将 $x$ 加入到序列的最后，并且将 $n$ 更新为 $n + 1$。

操作强制在线，我们设 $lastans$ 表示上一次操作 $0$ 的答案，初始值为 $0$。

对于所有操作 $0$，令 $l = (l\ \text{xor}\ lastans) \bmod n +1$，$r = (r\ \text{xor}\ lastans)\bmod n +1$，如果 $l > r$ 则交换两数。

对于所有操作 $1$，令 $x = x\ \text{xor}\ lastans$。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 10$，$1 \le n, m \le 5 \times 10 ^ 5$，$\sum n, \sum m \le 10 ^ 6$，$0 \le a_i, x < 2 ^ {30}$。

「2019 Multi-University Training Contest 1」Blank

题目链接：HDU 6578

有 $n$ 个格子排成一行，从左往右标号为 $1$ 到 $n$。

Tom 想要将每个格子填上 $\{0, 1, 2, 3\}$ 中的一个数字。但是他有 $m$ 条限制：第 $i$ 条限制为区间 $[l_i, r_i]$ 中必须有恰好 $x_i$ 种不同的数字。

请你求出满足所有限制的填数字的方案数量，答案对 $998244353$ 取模。

本题有 $T$ 组数据。

数据范围：$1 \le T \le 15$，$1 \le n \le 100$，$0 \le m \le 100$，$1 \le l_i \le r_i \le n$，$1 \le x_i \le 4$。

「Codeforces 1178F2」Long Colorful Strip

题目链接：Codeforces 1178F2

世界上有 $n +1$ 种不同的颜色，从 $0$ 到 $n$ 标号。现在你有一张长度为 $m$ 的纸，所有位置的初始颜色均为 $0$。

Alice 通过如下步骤队这张纸染色。她按顺序使用颜色 $1$ 到 $n$ 染色，对于第 $i$ 种颜色，她选择两个整数 $1 \le a_i \le b_i \le m$ 满足位置 $[a_i, b_i]$ 的颜色相同，然后把区间 $[a_i, b_i]$ 都染成颜色 $i$。

通过所有操作，Alice 需要把第 $i$ 个位置染成颜色 $c_i$，你需要求出满足条件的序列对 $\{a_i\}_{i = 1} ^ {n}, \{b_i\}_{i = 1} ^ {n}$ 的数量，答案对 $998244353$ 取模。

数据范围：$1 \le n \le 500$，$n \le m \le 10 ^ 6$，$1 \le c_i \le n$，$\forall 1 \le j \le n, \exists k, c_k = j$。

「TJOI 2019」唱、跳、rap 和篮球

题目链接：LOJ 3106

大中锋的学院要组织学生参观博物馆，要求学生们在博物馆中排成一队进行参观。

他的同学可以分为四类：一部分最喜欢唱、一部分最喜欢跳、一部分最喜欢 rap，还有一部分最喜欢篮球。如果队列中 $k, k + 1, k + 2, k + 3$ 位置上的同学依次，最喜欢唱、最喜欢跳、最喜欢 rap、最喜欢篮球，那么他们就会聚在一起讨论蔡徐坤。

大中锋不希望这种事情发生，因为这会使得队伍显得很乱。

大中锋想知道有多少种排队的方法，不会有学生聚在一起讨论蔡徐坤。两个学生队伍被认为是不同的，当且仅当两个队伍中至少有一个位置上的学生的喜好不同。

由于合法的队伍可能会有很多种，种类数对 $998244353$ 取模。

数据范围：$1 \le n \le 1000$，$0 \le a, b, c, d \le 500$，$a + b + c + d \ge n$。

「Luogu 4389」付公主的背包

题目链接：Luogu 4389

付公主有一个可爱的背包，这个背包最多可以装 $10 ^ 5$ 大小的东西。付公主有 $n$ 种商品，她要准备出摊了。每种商品体积为 $V_i$，都有 $10 ^ 5$ 件。

给定 $m$，对于整数 $s \in [1, m]$，请你回答用这些商品恰好装 $s$ 体积的方案数。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le V_i \le m \le 10 ^ 5$。

「Luogu 4841」城市规划

题目链接：Luogu 4841

阿狸的国家有 $n$ 个城市，现在国家需要在某些城市对之间建立一些贸易路线，使得整个国家的任意两个城市都直接或间接的连通。

为了省钱，每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案，如果存在一个城市对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。现在你需要求出一共有多少不同的方案。

换句话说，你需要求出 $n$ 个点的简单（无重边无自环）无向连通图数目。由于这个数字可能非常大，你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。

数据范围：$1 \le n \le 1.3 \times 10 ^ 5$。