「题目描述」

S国 有 $N$ 个 城市，编号从 $1$ 到 $N$ 。

城市间用 $N - 1$ 条双向道路连接，满足从一个城市出发可以到达其它所有城市。

每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰，为了方便，我们用不同的正整数代表各种宗教。

S国 的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在 信仰和他们相同 的城市留宿。当然旅程的终点也是信仰与他相同的城市。

S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级 总和 或 最大值。

在S国的历史上常会发生以下几种事件：

• CC x c ：城市 x 的居民全体改信了 c 教。
• CW x w ：城市 x 的评级调整为 w。
• QS x y ：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级总和。
• QM x y ：一位旅行者从城市 x 出发，到城市 y，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。

请根据这些信息，还原旅行者记下的数字。

为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

「题目链接」

BZOJ 3531 旅行 「SDOI 2014」

「题目描述」

我们称一个正整数 $N$是 幸运数，当且仅当它的十进制表示中不包含数字串集合 $S$ 中任意一个元素作为其子串。

例如当 $S = (22, 333, 0233)$ 时，$233$ 是幸运数，$2333$、$20233$、$3223$ 不是幸运数。

给定 $N$ 和 $S$，计算不大于 $N$ 的幸运数个数。

「题目链接」

BZOJ 3530 数数 「SDOI 2014」

「题目描述」

有一张 $n \times m $ 的数表。

其中第 $i$ 行第 $j$ 列 ($i \in [1, n], j \in [1,m] $) 的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。

每组询问给定 $a$，计算数表中不大于 $a$ 的数之和。

「题目链接」

BZOJ 3539 数表 「SDOI 2014」

「题目描述」

给定一个 $2$ 行 $N$ 列的网格图，每次询问一个区间内所有点的最小生成树，要求支持修改边权。

共 $M$ 次操作，$ 1 \leq N, M \leq 60000 $

「题目链接」

BZOJ 3995 道路修建 「SDOI 2015」

「题目描述」

设 $d(x)$ 为 $x$ 的约数个数，给定 $n, m$ ，求： $$ \sum_{i = 1}^n \sum_{j = 1}^m d(ij) $$ $n, m \leq 50000$ ，$T$ 组询问，$T \leq 50000$ 。

「题目链接」

BZOJ 3994 约数个数和 「SDOI 2015」

「题目描述」

3333 年，在银河系的某星球上，X 军团和 Y 军团正在激烈地作战。

在战斗的某一阶段，Y 军团一共派遣了 $N$ 个巨型机器人进攻 $X$ 军 团的阵地。

其中第 $i$ 个巨型机器人的装甲值为$A_i$ ，当一个巨型机器人的装甲值减少到 0 或者以下时，这个巨型机器人就被摧毁了。

X 军团有 $M$ 个激光武器，其中第 $i$ 个激光武器每秒可以削减一个巨型机器人 $B_i$ 的装甲值。

激光武器的攻击是连续的。

这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。

Y 军团看到自己的巨型机器人被 X 军团一个一个消灭，他们急需下达更多的指令。

为了这个目标，Y 军团需要知道 X 军团最少需要用多长时间才能将 Y 军团的所有巨型机器人摧毁。

但是他们不会计算这个问题，因此向你求助。

「题目链接」

BZOJ 3993 星际战争 「SDOI 2015」

「题目描述」

小C 有一个集合 $S$ ，里面的元素都是小于 $M$ 的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为 $N$ 的数列，数列中的每个数都属于集合 $S$ 。小C 用这个生成器生成了许多这样的数列。

但是 小C 有一个问题需要你的帮助：给定整数 $x$，求所有可以生成出的，且满足数列中所有数的乘积 $\mod M$ 的值等于 $x$ 的不同的数列的有多少个。

小C 认为，两个数列 $A$ 和 $B$ 不同，当且仅当至少存在一个整数 $i$ ，满足 $A_i \not = Bi$ 。

另外，小C 认为这个问题的答案可能很大，因此他只需要你帮助他求出答案 $\mod 1004535809$ 的值就可以了。

$1 \leq N \leq 10^9, 3 \leq M \leq 8000,M\text{ is a prime}, 1 \leq x \leq M - 1$ 。

「题目链接」

BZOJ 3992 序列统计 「SDOI 2015」

「题目描述」

给定一棵树，树中有一些关键点，每次询问 任取一点出发 **经过所有关键点 **并回到起点的 最短路径长度。

要求支持以下修改：将一个点设为关键点，或者取消一个关键点。

点数 $n \leq 100000$ ，操作数 $m \leq 100000$ 。

「题目链接」

BZOJ 3991 寻宝游戏 「SDOI 2015」

「题目描述」

小A 有一个 $1-2^N$ 的排列 $A[1 \dots 2^N]$ ，他希望将 $A$ 数组从小到大排序。

小A 可以执行的操作有 $N$ 种，每种操作最多可以执行一次，对于所有的 $i(1 \leq i \leq N)$，第 $i$ 种操作为将序列从左到右划分为 $2^{N-i+1}$ 段，每段恰好包括 $2^{i-1}$个数，然后整体交换其中两段。

小A 想知道可以将数组 $A$ 从小到大排序的不同的操作序列有多少个，小A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。

下面是一个操作事例:

$N=3, A[1 \dots 8] = [3, 6, 1, 2, 7, 8, 5, 4]$

第一次操作，执行第 3 种操作，交换 $A[1 \dots 4]$ 和 $A[5 \dots 8]$，交换后的 $A[1 \dots 8]$为 $[7,8,5,4,3,6,1,2]$ 。

第二次操作，执行第 1 种操作，交换 $A[3]$ 和 $A[5]$ ，交换后的 $A[1 \dots 8]$ 为 $[7, 8, 3, 4, 5, 6, 1, 2] $。

第三次操作，执行第 2 种操作，交换 $A[1..2]$ 和 $A[7..8]$,交换后的 $A[1..8]$ 为 $[1,2,3,4,5,6,7,8] $。

「题目链接」

BZOJ 3990 排序 「SDOI 2015」

【题目描述】

给定 $n, m$ ，求： $$ \sum_{i = 1}^n\sum_{j = 1}^m [\gcd(i, j) = p], \text{p is prime} $$ $n, m \leq 10^7$ 。

$T$ 组询问，$T \leq 10^4$。

【题目链接】

BZOJ 2820 YY 的 gcd