标签 多项式 下的文章
- 首页
- 多项式
「Luogu 4173」残缺的字符串
题目链接:Luogu 4173
很久很久以前,在你刚刚学习字符串匹配的时候,有两个仅包含小写字母的字符串 $A$ 和 $B$,其中 $A$ 串长度为 $m$,$B$ 串长度为 $n$。可当你现在再次碰到这两个串时,这两个串已经老化了,每个串都有不同程度的残缺。
你想对这两个串重新进行匹配,其中 $A$ 为模板串,那么现在问题来了,请回答,对于 $B$ 的每一个位置 $i$,从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配?
数据范围:$1 \le m \le n \le 3 \times 10 ^ {5}$。
「AHOI / HNOI 2017」礼物
题目链接:LOJ 2020
我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 $n$ 个装饰物,并且每个装饰物都有一定的亮度。
但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$(可能是负数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。
在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 $1, 2, \dots, n$,其中 $n$ 为每个手环的装饰物个数,第一个手环的 $i$ 号位置装饰物亮度为 $x_i$,第二个手环的 $i$ 号位置装饰物亮度为 $y_i$,两个手环之间的差异值为:
$$ \sum_{i = 1} ^ {n} (x_{i} - y_{i}) ^ {2} $$
麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小,这个最小值是多少呢?
数据范围:$1 \le n \le 5 \times 10 ^4$,$1 \le a_{i} \le m \le 100$。
「2019 Multi-University Training Contest 2」Fantastic Magic Cube
题目链接:HDU 6596
你有一个正整数 $n$ 和一个六元组集合,我们定义六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 的权值为 $\sum_{l_{x} \le x \le r_{x}, l_{y} \le y \le r_{y}, l_{z} \le z \le r_{z}} x \oplus y \oplus z$。
初始集合中只有一个元素 $(0, n - 1, 0, n - 1, 0, n - 1)$。接下来你要重复进行以下操作,直到集合的大小为 $n ^ 3$。
- 从集合中选择一个六元组 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 满足 $l_{x} < r_{x}$ 或 $l_{y} < r_{y}$ 或 $l_{z} < r_{z}$。
然后你需要从 $\{ x, y, z \}$ 中选择恰好一个元素,选择元素 $k$ 的条件是 $l_{k} < r_{k}$。
- 如果你选择了 $x$,接下来你需要选择一个整数 $t \in [l_{x}, r_{x})$,将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除,将 $(l_{x}, t, l_{y}, r_{y}, l_{z}, r_{z})$ 和 $(t +1, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
- 如果你选择了 $y$,接下来你需要选择一个整数 $t \in [l_{y}, r_{y})$,将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除,将 $(l_{x}, r_{x}, l_{y}, t, l_{z}, r_{z})$ 和 $(l_{x}, r_{x}, t + 1, r_{y}, l_{z}, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
- 如果你选择了 $z$,接下来你需要选择一个整数 $t \in [l_{z}, r_{z})$,将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, r_{z})$ 从集合中删除,将 $(l_{x}, r_{x}, l_{y}, r_{y}, l_{z}, t)$ 和 $(l_{x}, r_{x}, l_{y}, r_{y}, t + 1, r_{z})$ 加入集合。此时你将得到两个新的六元组的权值之积。
请你求出可以获得的最大权值,答案对 $998244353$ 取模。
本题有多组数据。
数据范围:$1 \le n \le 10 ^ 6$,$1 \le \sum n \le 3 \times 10 ^ 6$。
「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$。
「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 4841」城市规划
题目链接:Luogu 4841
阿狸的国家有 $n$ 个城市,现在国家需要在某些城市对之间建立一些贸易路线,使得整个国家的任意两个城市都直接或间接的连通。
为了省钱,每两个城市之间最多只能有一条直接的贸易路径。对于两个建立路线的方案,如果存在一个城市对,在两个方案中是否建立路线不一样,那么这两个方案就是不同的,否则就是相同的。现在你需要求出一共有多少不同的方案。
换句话说,你需要求出 $n$ 个点的简单(无重边无自环)无向连通图数目。由于这个数字可能非常大,你只需要输出方案数对 $1004535809 = 479 \times 2 ^ {21} + 1$ 取模的值即可。
数据范围:$1 \le n \le 1.3 \times 10 ^ 5$。
「Codeforces 438E」The Child and Binary Tree
题目链接:Codeforces 438E
我们的小朋友很喜欢计算机科学,尤其喜欢二叉树。
考虑一个含有 $n$ 个互不相同的正整数序列 $c_1, c_2, \dots, c_n$。如果一棵带点权有根二叉树满足其所有节点的权值都属于集合 $\{c_1, c_2, \dots, c_n\}$ 中,那么小朋友就会将其称作「好的」。并且他认为,这棵二叉树的权值是所有节点的权值总和。
给出一个整数 $m$,你需要对于所有整数 $s \in [1, m]$,计算出权值为 $s$ 的「好的」二叉树数量。答案对 $998244353$ 取模。
数据范围:$1 \le n, m, c_i \le 10 ^ 5$。