“华为杯”2025 年广东工业大学 ACM 程序设计竞赛
A. 出勤规划
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

橘猫发现了一个地图，这个地图上面居然有 maimai 的分布图！塑料一听就忍不住了，于是他把地图要了过来研究。

这张地图由 $$$n$$$ 个点和 $$$m$$$ 条带权无向边组成，现在我们定义 $$$f(u,v)$$$ 为点 $$$u$$$ 到点 $$$v$$$ 的最短距离。

塑料只关心其中的 $$$k$$$ 个点 $$$\{a_1,a_2,...,a_k\}$$$，于是他把这 $$$k$$$ 个点提取出来并记录下它们之间的距离，而这 $$$k$$$ 个点组成了一个新的无向图，边 $$$(i,j)$$$ 的权值为原图中的 $$$f(a_i,a_j)$$$。

就当塑料还在规划路线的时候，橘猫突然对这个新的无向图的最小生成树的所有边的权值之和很感兴趣，于是他把这个问题留给了塑料，但显然笨笨的塑料并不擅长解决这种问题，于是这个问题就交给你啦！

Input

本题有多组测试数据。

第一行输入一个数字 $$$T$$$ ($$$1 \leq T \leq 2 \times 10^4$$$)，表示有 $$$T$$$ 组数据；

接下来对于每组数据，第一行输入三个整数 $$$n,m,k$$$ ($$$1 \leq n \leq 5 \times 10^5$$$, $$$n-1 \leq m \leq 5 \times 10^5$$$, $$$1 \leq k \leq n$$$)，表示点的数量和边的数量；

接下来 $$$m$$$ 行，每行三个数字 $$$x,y,w$$$ ($$$1 \leq x,y \leq n$$$, $$$1 \leq w \leq 10^8$$$)，表示点 $$$x$$$ 到点 $$$y$$$ 有一条长度为 $$$w$$$ 的路径。

接下来一行 $$$k$$$ 个数字 $$$\{a_1,a_2,...,a_k\}$$$，表示塑料关心的这 $$$k$$$ 个点。

保证所有测试样例的 $$$n,m$$$ 之和均不超过 $$$5 \times 10^5$$$。

保证给出的图是连通的。

Output

对于每组测试样例，输出一个数字 $$$x$$$，表示这个最小生成树的边的权值之和。

Example
Input
2
5 4 3
1 2 3
1 3 5
1 4 7
2 5 6
3 4 5
3 6 3
1 2 4
1 3 5
2 3 2
3 2 7
1 1 4
2 2 6
1 2 3
Output
26
6
Note

第一组测试样例的原图和新图如下：

原图新图

可以发现：

  • $$$f(1,2) = 3, f(1,3) = 5, f(1,4) = 7, f(1,5) = 9$$$
  • $$$f(2,3) = 8, f(2,4) = 10, f(2,5) = 6$$$
  • $$$f(3,4) = 12, f(3,5) = 14$$$
  • $$$f(4,5) = 16$$$

其中，塑料只关心 $$$3,4,5$$$ 这三个点，可以发现最后的生成树只包含 $$$(3,4),(3,5)$$$ 这两条边，故生成树的权值为 $$$12+14=26$$$。

对于第二组测试样例：请注意可能有重边和自环。

B. 二分炼狱
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

塑料因为滥用 partition_point 被打入了二分炼狱，橘猫大人给他分配的第一个工作是 "给定一个正整数序列，询问下标查找右边第一个比它大/小的数字"。

"这不是我们 2023 新生月赛的题目吗，下次记得标明出处"，塑料洋洋洒洒地写了个线段树上二分（尽管这次并不需要修改）交了上去。

然而没过几天，橘猫发现塑料的代码出锅了。愤怒的橘猫给塑料发布了他的第二个工作：

定义一个函数 $$$f(x)$$$，它的工作方式是按顺序执行

  1. 初始时，下标 $$$pos = x$$$, $$$value = a_{pos}$$$ 所求和 $$$sum = 0$$$。
  2. 找到 $$$pos$$$ 右边第一个 $$$pos'$$$，使得 $$$a_{pos'} \gt value$$$，令 $$$sum$$$ 增加 $$$a_{pos'}$$$，$$$pos$$$ 修改为 $$$pos'$$$； 若找不到，返回 sum，结束。
  3. 找到 $$$pos$$$ 右边第一个 $$$pos'$$$，使得 $$$a_{pos'} \lt value$$$，令 $$$sum$$$ 增加 $$$a_{pos'}$$$，$$$pos$$$ 修改为 $$$pos'$$$； 若找不到，返回 sum，结束。
  4. 重新回到第 2 步。

塑料随便一想就想出了 $$$f(x)$$$ 的求法，然而橘猫大人让塑料别得意得太早，因为他希望对于每一个 $$$i$$$ ($$$1 \le i \le n$$$) 都要求出 $$$f(i)$$$ 的值。

汗流浃背的塑料发现时限只有 1ms，他找到了v2x1求他帮忙卡卡常数。v2x1一边流汗一边跟橘猫商量，最后橘猫同意塑料只需要在两秒内搞定。

然而就算如此塑料还是不会做，所以他来找你了，请你帮帮他吧。

Input

第一行输入一个正整数 $$$n$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$

接下来输入 $$$n$$$ 个正整数 $$$a_1,a_2,\dots,a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$，表示塑料需要处理的序列。

Output

设 $$$b_i$$$ 为第 $$$i$$$ 个元素带入 $$$f(x)$$$ 的返回值，你需要输出一个长度为 $$$n$$$ 的正整数序列 $$$b_1,b_2,...,b_n$$$，元素之间用空格隔开。

Example
Input
6
1 1 4 5 1 4
Output
4 4 6 0 4 0
Note

样例解释：

对于第一个元素，第一个比它大的数是 $$$4$$$，而之后就没有比 $$$1$$$ 小的数字了，所以 $$$b_1 = 4$$$。

对于第三个元素，第一个比它大的数是 $$$5$$$，接下来比它小的第一个数字是 $$$1$$$，所以 $$$b_3 = 5 + 1 = 6$$$。

C. BloomsTD6
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

猴村遭受了气球的入侵，众猴不知所措之时，回旋镖猴淡笑一声表示："很简单，我成尊不就是了?"，说完，不再掩饰气息，显露出 $$$555$$$ 修为。

猴村发现有 $$$m$$$ 个气球正在靠近，它们分别在 $$$a_1, a_2, \dots, a_m$$$ 时刻出现在 $$$(x_1,y_1)$$$，并以 $$$1$$$ 单位/秒的速度沿着一条路径 $$$\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$$$ 移动。

此时，回旋镖猴站在 $$$(ta_x, ta_y)$$$，索敌半径为 $$$2r$$$；每次攻击时，回旋镖猴会选择当前攻击范围内还未被击破的生成时间最早的气球，然后向该气球抛出一个回旋镖，并会瞬间击破所有与其运动轨迹距离不超过 $$$10^{-8}$$$ 的气球。回旋镖的轨迹是以他为起点的一个逆时针方向的半径为 $$$r$$$ 的圆，且目标气球位于轨迹的前半段。

回旋镖猴会在气球进入攻击范围内时进行攻击，但回旋镖猴每次攻击后需要 $$$gap$$$ 时间休息，然后才能进行下一次攻击。

当气球走出路径后，回旋镖猴便失败。请问回旋镖猴能否守住猴村呢？

Input

第一行输入五个正整数 $$$n, ta_x, ta_y, r, gap$$$ ($$$2 \leq n \leq 10^5$$$, $$$-10^3 \leq ta_x,ta_y \leq 10^3$$$, $$$1 \leq r,gap \leq 10^3$$$)，分别表示路径点数量，气球数量，回旋镖猴的初始坐标、索敌半径和攻击间隔；

接下来 $$$n$$$ 行，每行输入两个整数 $$$x_i,y_i$$$ ($$$-10^3 \leq x_i,y_i \leq 10^3$$$)，表示第 $$$i$$$ 个路径点的坐标； 第 $$$n+2$$$ 行，输入一个正整数 $$$m$$$ ($$$1 \leq m \leq 10^3$$$)，表示气球数量；

第 $$$n+3$$$ 行，输入 $$$m$$$ 个整数 $$$a_1,a_2,\dots,a_m$$$ ($$$0 \leq a_1 \leq a_2 \leq ... \leq a_m \leq 5 \times 10^4$$$)，表示气球出现的时间。

保证回旋镖猴不会出现在路径上。

Output

若守得住，你应当输出 Yes 后输出结束时间（即最后一个气球被击破的时间）；

若守不住，你应当输出 No 后输出第一个冲破防守的气球的编号。

本题采用 Special Judge，你的输出答案和标准答案相对误差小于 $$$10^{-6}$$$ 即视作正确。

你可以以任意大小写输出 Yes 和 No（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定的回答）。

Examples
Input
5 2 2 2 4
0 0
4 0
4 4
0 4
0 0
6
0 1 2 3 4 5
Output
Yes
20.0000000000
Input
5 20 6 5 12
12 0
12 12
0 12
0 0
12 0
5
0 12 24 36 48
Output
Yes
48.0000000000
Input
5 3 1 1 1
0 0
1 0
1 1
0 1
0 0
5
0 1 2 3 4
Output
Yes
6.0000000000
Note

第一组测试样例中，当 $$$t = 4$$$ 时，气球与回旋镖猴的位置可参考下图：

注意当 $$$t=0$$$ 时，第一个气球出来瞬间被回旋镖猴击破了。

D. 橘猫的背包问题
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

一天，橘猫打算教塑料 01 背包，经过一番惊心动魄的讲解，塑料总算是略懂一二。

在课程结束时，橘猫打算布置 $$$10^4$$$ 个 01 背包的作业给塑料，但是造 $$$10^4$$$ 个题的数据疑似有点太麻烦了，于是他想了一道新题目：

"橘猫有 $$$n$$$ 个价格、价值不等的物品，第 $$$i$$$ 个物品的价格为 $$$p_i$$$，价值为 $$$v_i$$$。

现在塑料要来购买橘猫的物品。橘猫将所有物品按照编号顺序排成一排，并选定了一段编号区间 $$$[L,R]$$$，要求塑料只能购买编号在区间 $$$[L,R]$$$ 内的物品。

已知塑料带了 $$$P$$$ 块钱过来，请你输出他买到的物品的价值之和的最大值。

但为了让你加深对 $$$01$$$ 背包的印象，接下来我会给出 $$$Q$$$ 次独立的询问，每次询问会给出塑料可以购买的物品的编号区间和塑料携带的金额，对于每次询问，你都要输出他买到的物品的价值之和；

同时，为了让你能够老老实实地做 $$$Q$$$ 次 $$$01$$$ 背包，本题强制在线。"

塑料写了一个对每个询问区间都跑一遍 $$$01$$$ 背包的解法，但是太慢了 TAT，他希望可以尽快得到结果，于是他找到了正在参加校赛的你，请你帮帮他。

Input

本题每个测试点仅有一组测试数据。

第一行输入一个正整数 $$$n$$$ ($$$1 \leq n \leq 10^3$$$)，表示物品的数量；

第二行输入 $$$n$$$ 个正整数 $$$p_1,p_2,...,p_n$$$ ($$$1 \leq p_i \leq 10^4$$$)，表示物品的价格；

第三行输入 $$$n$$$ 个正整数 $$$v_1,v_2,...,v_n$$$ ($$$1 \leq v_i \leq 10^5$$$)，表示物品的价值；

第四行输入一个正整数 $$$Q$$$ ($$$1 \leq Q \leq 10^4$$$)，表示塑料的个数；

接下来 $$$Q$$$ 行，每行给出第 $$$i$$$ 个塑料可以挑选的编号区间和他携带的金额的加密值 $$$iL_i$$$, $$$iR_i$$$, $$$iP_i$$$ ($$$0 \leq iL_i,iR_i \leq n$$$, $$$0 \leq iP_i \leq 10^4$$$)。

为了得到真实的 $$$L_i$$$, $$$R_i$$$, $$$P_i$$$，你需要进行以下解密：

设 $$$last$$$ 为上一次询问的答案（第一次询问时 $$$last = 0$$$），则

$$$L_i = ((iL_i + last) \bmod n) + 1$$$

$$$R_i = ((iR_i + last) \bmod n) + 1$$$

此时若 $$$L_i \gt R_i$$$，则交换 $$$L_i$$$ 和 $$$R_i$$$。

$$$P_i = ((iP_i + last) \bmod 10000) + 1$$$

Output

对于每组测试数据的每个询问，输出一个正整数 $$$x$$$，表示塑料能够购得物品的最大价值。

Example
Input
5
2 3 1 5 4
3 4 1 2 8
3
2 3 7
1 5 2
2 5 6
Output
3
8
10
Note

解密后的 $$$L_i$$$, $$$R_i$$$, $$$P_i$$$ 如下：

第一组的 2 3 7 解密后为 3 4 8

第二组的 1 5 2 解密后为 4 5 6

第三组的 2 5 6 解密后为 1 4 15。

E. GDUT = 1
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

塑料在刷短视频的时候看到了以下问题：

$$$\overline{a}+\overline{aa}+\overline{a}+\overline{aa}+\overline{a}=100$$$，求 $$$a$$$。

看到 "二年级" 字眼的他很快反应过来这 $$$\overline{aa}$$$ 并非是 $$$a^2$$$，而是一个个位和十位都是 $$$a$$$ 的二位数！

正在此时传说中的灵感大王跑过来，兴冲冲地把这道题留下来了：

给你一个由 $$$G$$$、$$$D$$$、$$$U$$$、$$$T$$$ 和若干 $$$+$$$ 号组成的合法式子，问能否将 $$$G$$$、$$$D$$$、$$$U$$$、$$$T$$$ 替换为某个 $$$0 \sim 9$$$ 的数字可以使得式子等于给定的值。"有的话还要构造一个合法方案哟！"

"好好好"，塑料把这个题记录了下来，并相信你可以给出正确的答案。

因为塑料希望减轻你的负担，他特别允许你构造的式子中的数可以出现前导 $$$0$$$。

Input

本题有多组测试样例。

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 10^5$$$)，表示有多组测试样例；

接下来每组测试样例输入一行，包含一个长度为 $$$n$$$ ($$$1 \leq n \leq 5 \times 10^5$$$) 的字符串和一个正整数 $$$x$$$ ($$$0 \leq x \leq 10^{18}$$$)，表示灵感大王留下来的式子和给定的值。

保证单个测试点的所有式子长度之和不超过 $$$10^6$$$。

Output

对于每个测试样例，

如果有解，先输出一行 YES，然后输出 $$$4$$$ 个数字，表示你所构造的结果；

如果无解，你只需要输出一行 NO。

你可以以任意大小写输出 Yes 和 No（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定的回答）。

Example
Input
3
GDUT 1
GD+UT 98
DDT 123
Output
YES
0 0 0 1
YES
4 4 5 4
NO
Note

对于第二组样例，5 4 4 4 也是一组可行的解。

F. 排队
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

伍六七的理发店里突然来了一群 Capoo！但由于已经是下班时间所以 Capoo 们打算第二天再来。

然而，Capoo 们的起床时间有所不同，于是一番商量后，领头的 Capoo 递来了一张预约表，上面写着第 $$$i$$$ 只 Capoo 的预约时间为 $$$t_i$$$。

但是 Capoo 实在是太多了！为了应对如此多的 Capoo，伍六七不得不找到隔壁的杀马特协商，经过研究后他们决定将这 $$$n$$$ 只排队的 Capoo 从中间划分成连续的两部分（可以为空）$$$\dagger$$$，前半部分由杀马特负责，后半部分由伍六七负责，而他们给 Capoo 理发所需时间都为 $$$k$$$，这意味着，若伍六七/杀马特在第 $$$l$$$ 秒开始给 Capoo 理发，则他在 $$$[l,l+k)$$$ 这段时间内都在给这只 Capoo 理发而不能给其他 Capoo 理发。如果某只 Capoo 来的时候若伍六七/杀马特正在给其它 Capoo 理发，那它就只好排队等候直到轮到它理发。

现在问题是如何确定一个最佳的划分，使得所有 Capoo 的等待时间之和最小——这里对于第 $$$i$$$ 只 Capoo，它的等待时间为 $$$(\text{开始理发时间} - \text{到达时间})$$$。

为了集思广益，塑料把这道题丢到了校赛里，并期待你给出一个最佳的划分，而你只需要输出最小的等待时间之和，这样塑料就不需要写 spj 了 OuO

$$$\dagger$$$ 对于队列 $$$[1,2,3,4,5]$$$，可能的划分为：$$$[1,2]$$$ 和 $$$[3,4,5]$$$、$$$[1,2,3,4,5]$$$ 和 $$$[]$$$；不允许的划分：$$$[1,2,4]$$$ 和 $$$[3,5]$$$，因为元素在原数组中不连续。

Input

本题有多组测试数据。

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 2\times 10^4$$$)，表示有 $$$T$$$ 组样例；

接下来对于每组测试样例：

第一行输入两个正整数 $$$n$$$ ($$$1 \leq n\leq 2 \times 10^5$$$) 和 $$$k$$$ ($$$1 \leq k \leq 10^8$$$)，表示 Capoo 的数量和给某只 Capoo 理发所需时间；

第二行输入 $$$n$$$ 个正整数，其中第 $$$i$$$ 个数表示第 $$$i$$$ 只 Capoo 的预约时间 $$$t_i$$$ ($$$1 \leq t_i \leq 10^8$$$)。

保证所有测试样例的 $$$n$$$ 之和不超过 $$$5 \times 10^5$$$。

Output

对于每组测试样例，输出一行一个正整数 $$$w$$$，表示最小等待时间之和。

Examples
Input
3
3 5
1 1 4
5 4
4 1 7 2 6
6 3
1 1 1 1 1 1
Output
2
3
18
Input
2
6 57
80 60 27 22 71 66
9 69
13 18 16 32 44 27 24 15 12
Output
163
1015
Note

对于第一个样例组的第二组测试样例：

如果选择将序列划分为 $$$[1,4)$$$ 和 $$$[4,5]$$$，则等待时间计算如下：

对于杀马特负责的部分，

$$$t=1$$$ 时编号为 $$$2$$$ 的 Capoo 到达，杀马特开始为其理发；

$$$t=4$$$ 时编号为 $$$1$$$ 的 Capoo 到达，但此时杀马特还在为编号为 $$$2$$$ 的 Capoo 理发，需要排队等到 $$$t=5$$$ 时才轮到它；

$$$t=7$$$ 时编号为 $$$3$$$ 的 Capoo 到达，但此时杀马特还在为编号为 $$$1$$$ 的 Capoo 理发，需要排队等到 $$$t=9$$$ 时才轮到它。

故这三只 Capoo 的等待时间之和为 $$$1+2=3$$$，而伍六七负责的两只 Capoo 均不需要等待，故总等待时间为 $$$3+0=3$$$。

可以证明不存在更优的方案。

G. Jump Sort
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

塑料从 u2x1 那拿到了一个长度为 $$$n$$$ 的排列$$$\dag$$$，打算给它排个序，使得这个排列变为升序。

塑料有一种神奇的魔法。在排序前，他将选择一个 $$$x$$$ ($$$1 \leq x \leq n$$$)，接下来，他将进行以下操作任意次（当然可以是 $$$0$$$，如果本身已经有序）：

  • 选择距离为 $$$x$$$ 的两个下标 $$$i$$$ 和 $$$j$$$（即满足$$$|i - j| = x$$$），并交换 $$$a_i$$$ 和 $$$a_j$$$。

在排序开始前，他想知道有多少个 $$$x$$$ 可以帮助他使得排列最终有序，但是笨笨塑料并不知道怎么做，所以请你帮帮他吧！

$$$\dag$$$ 在这里，我们定义一个长度为 $$$n$$$ 的排列为一个包含从 $$$1$$$ 到 $$$n$$$ 这 $$$n$$$ 个不同的整数的序列，且每个整数恰好出现一次。

Input

第一行输入一个正整数 $$$n$$$ ($$$1 \leq n \leq 5 \times 10^5$$$)，表示序列长度；

第二行输入一个长度为 $$$n$$$ 的排列 $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq n$$$)。

Output

输出一个正整数 $$$ans$$$，即有多少个 $$$x$$$ 可以帮助塑料完成排序。

Example
Input
4
3 2 1 4
Output
2
Note

样例解释：

  • $$$x = 1$$$ 时，一种可能的排序过程如下：
  • $$$3 ~ 2 ~ 1 ~ 4 \to 3 ~ 1 ~ 2 ~ 4 \to 1 ~ 3 ~ 2 ~ 4 \to 1 ~ 2 ~ 3 ~ 4$$$
  • $$$x = 2$$$ 时，塑料可以将 $$$1$$$ 和 $$$3$$$ 互换完成排序。
  • $$$x = 3,4$$$ 时，可以证明不存在可行的排序方法。

所以答案为 $$$2$$$。

H. 可爱串串
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

塑料有一个长度为 $$$n$$$ 的 $$$01$$$ 串 $$$S$$$。

定义一个 $$$01$$$ 串的可爱值为这个 $$$01$$$ 串中 $$$1$$$ 的数量减去 $$$0$$$ 的数量；

塑料将要从中间选一个位置将这个 $$$01$$$ 串切成连续且非空的两半。

他想要知道切开后这两个串的可爱值的乘积最大可以是多少，但他非常懒，想要你帮他算一下，并承诺算对了会给你一发 AC 作为奖励。

Input

输入包含多组测试数据。

第一行一个正整数 $$$T$$$ ($$$1 \leq T \leq 50000$$$)，表示数据组数；

接下来对于每组测试数据，输入两行：

数据的第一行输入一个正整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$)，表示字符串长度；

数据的第二行输入一个长度为 $$$n$$$ 的 $$$01$$$ 串 $$$S$$$。

保证对于每个测试点下所有测试数据的 $$$n$$$ 之和不超过 $$$5 \times 10^5$$$。

Output

对于每组测试数据，输出一个整数 $$$x$$$，表示题目中式子的最大值。

Example
Input
5
3
100
4
1011
6
111011
3
111
8
11111111
Output
0
1
4
2
16
Note

以最后一组样例为例，

若选择 $$$pos=2$$$，则乘积为 $$$2 \times 6 = 12$$$；

若选择 $$$pos=4$$$，则乘积为 $$$4 \times 4 = 16$$$。

可以证明，$$$16$$$ 即为乘积的最大值。

I. 好想成为人类啊
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

丰川祥子一直在寻找成为人类的方法。上了大学之后，她加入了本校的 ACM 集训队，并开始打 Codeforces。

一天，她正如往常一样打算参加 Codeforces 线上比赛时，却不料点进去看到的是 Cloudflare 的验证码。这个验证码的要求居然是这样的：

  • 我们定义 $$$S[l;r]$$$ 是 $$$S$$$ 的一个连续的子串 $$$S_{l}S_{l+1}\cdots S_{r}$$$ ($$$1\le l \le r \le |S|$$$)

  • 若字符串 $$$S$$$ 的某段子串 $$$S[l;r] = T$$$，那么我们就说 $$$[l,r]$$$ 是字符串 $$$T$$$ 的一个出现区间。

  • 给定字符串 $$$S$$$ 和字符串 $$$T$$$，你需要选取一个标记集合 $$$a = \{a_1,a_2,...,a_k\}$$$，使得对于每个出现区间 $$$[l, r]$$$，都存在一个 $$$a_i$$$ $$$(1 \leq i \leq k)$$$，满足 $$$l \leq a_i \leq r$$$。

例如，当 $$$S = \texttt{ababa}$$$ 且 $$$T = \texttt{aba}$$$ 时，出现区间为 $$$[1,3]$$$ 和 $$$[3,5]$$$，而祥子只需要标记集合 $$$\{3\}$$$ 即可覆盖两个区间，也可以选择标记集合 $$$\{1,5\}$$$，这样也可以覆盖两个区间，她甚至可以选择标记集合 $$$\{1,2,3,4,5\}$$$，但是这样就得点 $$$5$$$ 下，很麻烦。 擅长键盘的 Saki 酱很快就敲出了 "在一个字符串找另一个字符串的所有出现位置" 的代码，但她希望以尽量少的标记次数来完成本次验证，尽快成为人类！

塑料看完这一集之后立刻把这个问题丢给了你。你的任务就是输出最小的满足条件的标记集合的大小。

Input

输入包含多组测试数据。

第一行包括一个正整数 $$$T$$$ $$$(1 \leq T \leq 10^4)$$$，表示数据组数；

接下来对于每组测试数据：

第一行输入两个正整数 $$$n$$$ 和 $$$m$$$ $$$(1 \leq n,m \le 10^3)$$$，表示字符串 $$$S$$$ 和 $$$T$$$ 的长度；

接下来一行输入一个长度为 $$$n$$$ 的字符串 $$$S$$$;

接下来一行输入一个长度为 $$$m$$$ 的字符串 $$$T$$$。

保证所有字符串都由英文小写字母构成。

保证每个测试点所有测试数据的 $$$n$$$ 之和与 $$$m$$$ 之和均不超过 $$$2^{14}$$$。

Output

对于每组测试数据，输出一行一个非负整数 $$$x$$$，表示最小的满足条件的标记集合的大小。

Example
Input
2
5 3
ababa
aba
20 4
sakisakisakisakisaki
miku
Output
1
0

J. 11 背包
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

猫猫有 $$$n$$$ 个物品，第 $$$i$$$ 个物品的质量为 $$$a_i$$$，现在猫猫打算把它们全部装到背包里，可是他发现只有一大堆容量都为 $$$m$$$ 的背包。

虽然猫猫很想用尽量少的背包装下所有物品，但这实在是太复杂了，导致他经常会错过最优解，于是他干脆摆烂了：

  • 猫猫会先准备 $$$x$$$ 个空的背包，接下来他每次从所有未装入背包的物品中任意选一个然后放入任意一个尚能放下此物品的背包里，直到物品全部放入背包为止。

他想知道，最少要准备多少个背包，才能保证他无论如何操作，最终都能将所有物品放入背包内。

这个问题就交给你了！

Input

每个测试点有多组测试数据。

第一行输入数据组数 $$$T$$$ ($$$1 \leq T \leq 100$$$)，表示有 $$$T$$$ 组数据；

接下来对于每组测试数据，

第一行输入两个正整数 $$$n,m$$$ ($$$1 \leq n \leq 20$$$, $$$1 \leq m \leq 10^9$$$)，分别表示物品的数量和背包的容量；

第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,...,a_n$$$ ($$$1 \leq a_i \leq m$$$)，表示每个物品的大小。

保证每组测试数据中，$$$n \geq 15$$$ 的数据点不超过 $$$5$$$ 个。

Output

对于每组测试数据，输出一个正整数 $$$x$$$，表示最少需要准备 $$$x$$$ 个背包。

Example
Input
3
5 10
6 5 4 3 2
3 2
1 1 2
1 5
4
Output
3
3
1
Note

对于第一组测试样例，若只有两个背包，则猫猫可以：

  • 先把第一个物品放到第一个背包；
  • 再把第二个物品放到第二个背包；
  • 再把第三个物品放到第二个背包；
  • 再把第四个物品放到第一个背包；
  • 最后剩下第五个物品，无法放入任何一个背包。

可以证明，若猫猫有三个背包，则无论以何种顺序放入物品均能装下。

K. 橘猫的后缀问题
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

今天橘猫打算教塑料后缀数组，只见他端上来一个长度为 $$$n$$$ 的由小写字母组成的字符串，问塑料某个后缀在所有后缀中排第几大，然而塑料直接掏出了板子干掉了，还嘲讽了一番。

面对如此场景，橘猫灵机一动，给塑料布置了一道新题目：

给你一个长度为 $$$n$$$ 的由小写字母组成的字符串 $$$S$$$，接下来会有 $$$Q$$$ 次查询/修改操作：

  • 1 x c：修改操作，将位置 $$$x$$$ 的字符改为 $$$c$$$；

  • 2 x：查询操作，询问 $$$S$$$ 的从第 $$$x$$$ 位开始的后缀$$$\dagger$$$的排名。

我们定义后缀的排名为在 $$$S$$$ 所有后缀中按字典序排序后该后缀的下标（从 $$$1$$$ 开始）。

字典序的定义为，对于两个字符串 $$$s$$$ 和 $$$t$$$，找到左起第一个不同的字符 $$$s_i$$$ 和 $$$t_i$$$。若找不到，则长度更短的字符串字典序更小；否则按字母表升序比较 $$$s_i$$$ 和 $$$t_i$$$。

塑料看到这道新题心生怯意，于是他请你帮他做这道题，不过他发现了题目的最下方还有一行字：

保证初始字符串的每个字符和更新操作给出的每个字符都是从 {a,b,...,z} 中均匀随机抽取的。

$$$\dagger$$$ 对于一个字符串 $$$s$$$，从第 $$$x$$$ 位开始的后缀为 $$$s_{x}s_{x+1}\dots s_n$$$ 如字符串 abcde 的从第 $$$3$$$ 开始的后缀为 cde。

Input

本题每个数据点仅有一组测试样例。

第一行输入一个正整数 $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$)，表示字符串 $$$S$$$ 的长度；

第二行输入一个长度为 $$$n$$$ 的字符串 $$$S$$$；

第三行输入一个正整数 $$$Q$$$ ($$$1 \leq Q \leq 2 \times 10^5$$$) 表示询问次数；

接下来 $$$Q$$$ 行，每行的输入格式为 1 x c ($$$1 \leq x \leq n, c \in \{a,b,...,z\}$$$) 或 2 x ($$$1 \leq x \leq n$$$)，对应上述操作。

Output

对于每个询问操作，输出一个正整数 $$$x$$$ 表示目标后缀的排名。

Example
Input
5
abbaa
3
2 3
1 1 b
2 3
Output
4
3
Note

样例仅为了方便理解题面作参考，不符合数据性质

在第一次询问时，后缀的排名如下：

  • 5 a
  • 4 aa
  • 1 abbaa
  • 3 baa
  • 2 bbaa

故长度为 $$$3$$$ 的后缀排名为 $$$4$$$；

在第二次询问时，后缀的排名如下：

  • 5 a
  • 4 aa
  • 3 baa
  • 2 bbaa
  • 1 bbbaa

故长度为 $$$3$$$ 的后缀排名为 $$$3$$$。

Statement is not available in English language
M. 晚饭吃什么？
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

"晚饭吃什么？" "我都行。"

notPP 罗列了 $$$m$$$ 个吃饭的地点，在接下来的 $$$n$$$ 天中，notPP 觉得一直吃外卖会腻，于是他决定拿恰好 $$$k$$$ 天出来去外面吃饭。

但连续两天都在同一个地方吃饭容易腻，于是他希望"不能连续两天都去同一个地方吃饭（外卖除外）"的规则。

在这种情况下，请问 notPP 有多少种方案呢？因为答案可能很大，所以请将其对 $$$10^9+7$$$ 取模。

Input

本题每个测试点有多组测试数据。

第一行输入一个正整数 $$$T$$$ ($$$1 \leq T \leq 10^5$$$)，表示有 $$$T$$$ 组测试样例。

接下来对于每组样例：

一行输入三个数字 $$$n,m,k$$$ ($$$1 \leq k \leq n \leq 10^6$$$, $$$1 \leq m \leq 10^6$$$)，分别代表接下来 $$$n$$$ 天，有 $$$m$$$ 个吃饭的地方和分配 $$$k$$$ 天。

保证单个测试点的所有测试数据的 $$$n$$$ 之和不超过 $$$10 ^ 6$$$。

Output

输出一行，表示分配方案的数量对 $$$10^9+7$$$ 取模得到的结果。

Example
Input
2
3 2 3
3 2 2
Output
2
8
Note

对于第一个样例，notPP 在接下来的 $$$3$$$ 天都去外面吃，故有两种情况：$$$\{1,2,1\}$$$ 和 $$$\{2,1,2\}$$$。

对于第二个样例，这里有所有的可行情况（其中 $$$0$$$ 表示外卖）：

$$$\{1,2,0\},\{2,1,0\},\{1,0,1\},\{1,0,2\},\{2,0,1\},\{2,0,2\},\{0,1,2\},\{0,2,1\}$$$