#8. 小w、小j和小z

小z告诉小w了这样一道送分题。

在数轴上有n个小人,第i个人现在在pi位置,速度是vi(速度的正负代表不同的方向)。如果某一时刻两个人在同一位置,那么就会发生碰撞。

如果现在小j可以使用能力,使得其中k个人凭空消失,那么最多会有多长时间内,没有任何两个人会碰撞呢?

输入格式

一行两个整数 nk

接下来 n行,每行两个整数pi,vi,表示每个人的初始位置和速度。

输出格式

如果时间是无限长,输出Forever, 否则输出一个实数表示答案,答案误差小于103即可。

样例一

input

4 1 
1 1 
3 -1 
5 2 
7 -2

output

1.00

样例二

input

4 2 
1 1 
3 -1 
5 2 
7 -2

output

Forever

数据范围和约定

本题采用捆绑测试,对于全部数据,1kn105;|pi|,|vi|109.

子任务编号 分值 n k
11020n
22020010
315n
415200010
520n
620105

时间限制:2s

空间限制:256MB

下载

样例数据下载

#9. 小h的树

作为绿色的使者,小h有棵n个节点的带权树。

找出k个点A1,A2,,Ak

使得i=1k1dis(Ai,Ai+1)最小。

其中dis(i,j)表示点i到点j的树上最短路。

输入格式

第一行两个正整数n,k,表示树的顶点数和需要选出的点个数。

接下来n1行每行3个非负整数x,y,z,表示从存在一条从xy权值为z的边。

1kn

1x,yn

1z105

输出格式

一行一个整数,表示最小的距离和。

样例一

input

5 4
1 2 1
2 3 3
2 4 2
4 5 5

output

7

数据范围

对于10%的数据,  n10

对于另外10%的数据, k=n

对于另外20%的数据, n50

对于另外20%的数据, n200

对于100%的数据,  n3000

时间限制:1s

空间限制:256MB

下载

样例数据下载

#10. 小x的城池

作为国家的管理者,小 x 新开拓的有 n 做城池,这 n 座城池排成一条直线,依次编号为 1n,初始时对于所有 i[1,n1] 城市 i 到城市 i+1 有单向道路。

每个城市都有一个等级 A 或者 B,A 级市更高一些,所以按理来说应该拥有更多的人口。不过有的 A 级市可以通过道路到达人口更多的 B 级市,那么这个 A 级市就有被降级的危险,我们称这个 A 级市是危险的。

现在小 x 列出了一系列改造计划,希望你能实时跟进这些计划,并时刻告诉他有多少个 A 级城市是危险的。

改造计划有两种:

UPDATE x y: 人口迁移政策,把第 x 个城市的人口修改为 y

REVERSE l r: 道路修改计划,把第 l 个城市到第 r 个城市之间的道路全部翻转(每条道路改变朝向,而不是拿出一条链反过来接回去)。

对于每个计划,输出一行一个正整数表示修改之后危险的 A 级城市的数目。

输入格式

第一行两个正整数 n,Q 表示城市数和询问数。

接下来 n 行,每行一个整数和一个字符(只能是A,BPi,c,表示每个城市的人口和等级。

接下来 Q 行,每行如下:

UPDATE x y

REVERSE l r

如题意表示一次改造。

输出格式

对于每个操作输出一行一个整数表示答案。

样例一

input

7 4
0 A
13 B
4 B
11 B
10 A
12 B
4 A
REVERSE 2 5
UPDATE 5 12
REVERSE 5 7
UPDATE 2 0

output

2
2
3
1

样例二

见样例数据下载。

限制与约定

本题采用捆绑测试,对于全部数据,1N,Q105;1xn;1lrn;0Pi,y75.

子任务编号 分值 n,Q 约定
110103
235105没有 REVERSE 操作
335没有 UPDATE 操作
420

时间限制:4s

空间限制:233MB

下载

样例数据下载

#11. A

小w要造一个送分的置换。所谓置换,就是两排1n的数字用括号括起来。比如 (1234525431) 就是一个置换,它表示的是把本来在1位置的数字变换到位置2,把在2位置的数字变换到位置5,etc.

然而小w的妹妹jz患有阅读障碍,在她的眼里,数字i会被看成数字ai,其中a是一个排列,也就是说ij aiaj。小w非常疼爱自己的妹妹jz,可是他却因为不知道排列a,难以理解自己的妹妹。

为了能更好的理解自己的妹妹,他想要知道,对于一个置换(1inp1pipn),她的妹妹眼里的置换有多少种本质不同的可能呢?答案对998244353取模后输出。

两个置换本质相同当且仅当每次交换两列把第一排数排好序之后,第二行数相同。

输入格式

第一行一个整数n

第二行一共n个整数,p1,p2,,pn

输出格式

一行一个整数表示对998244353取模之后的答案。

样例一

input

5
2 1 4 5 3

output

20

数据范围

时间限制1s, 空间限制256MB

测试点编号 n的规模 约定
1,210
3,41000
5106保证pi=i+1,pn=1
6,7106保证置换每个轮换的大小互不不同
8,9,10106
#12. B

小w是一个热心肠的少年,这天,他来到了肥宅聚集地,用吸脂手术帮助肥宅减肥。

这里聚集着 n 个肥宅,第 i 个肥宅的体重为 bi,每过一天,每个肥宅的体重就会增加 ai。小w每天只能进行一场手术,为一个体重为 c 的肥宅做手术,小w的成本也为 c

因为时间有限,小w准备只帮助 k 个肥宅,请问小w最小需要花费多少成本呢?

输入格式

第一行两个整数,nk

接下来 n 行,每行两个整数 aibi,表示第 i 个肥宅的身体指标。

输出格式

一行一个整数,表示小w最小要花费的成本。

样例一

input

3 3
1 0
2 1
3 2

output

7

样例二

input

3 3
5 4
2 3
6 1

output

17

数据范围

时间限制1s,空间限制512MB

测试点编号 n的规模 ai,bi的规模
1,2n20ai106,bi1011
3,4n2000
5,6n105
7,8,9,10n106
#13. C

小w高考之后,为了和同学出去旅游,想要知道每个城市两两之间的最短距离。

小w生活的国家,是一个有n个城市的小国,城市之间有m条权值为1的无向边相连。

小y一眼就看出来这是一个经典的多最短路问题,不过因为小w并不是一个斤斤计较的人,他只想知道大致的距离。

如果两点间距离为d,那么输出d, d+1或者d+2,都算正确。

聪明的你能帮助小w规划他的旅行吗?

为了加速输出,小w只会询问q对点之间的距离。

输入格式

一行两个整数n,q

之后n行,每行一个长度为n的01串。输入一个01矩阵。

Ai,j=1表示ij之前有边,Ai,j=0表示ij之间没有边。保证矩阵是对称的,Ai,j=Aj,i

接下来q行,每行两个整数a,b,表示询问ab之间的最短路径。

输出格式

q行,每行输出一个答案,只要在[ans,ans+2]的区间内,就算正确。如果不连通,输出998244353

样例一

input

5 5
11111
11111
11111
11111
11111
1 2
1 3
2 3
4 2
5 1

output

3
1
1
2
2

数据范围

时间限制2s, 空间限制512MB

测试点编号 n的规模 q的规模
1,2n500 q105
3,4,5,6n2000
7,8,9,10n4000
#14. A

小w负责a国的火车系统调度。a国的火车系统由m条铁轨构成,每条火车线路形如(a,b,c)的形式,表示有两辆火车在c时刻,分别从a地和b地出发前往对面。由于a国科技发达,我们可以认为火车不需要时间,在c时刻出发就可以在c时刻到达。

为了从xy,小w可能会换乘一系列的铁路线路,小w为了从第一个铁路线路(a1,b1,c1)换乘第二个铁路线路(a2,b2,c2),需要c1c2,b1=a2

现在有q个询问,每个询问问小w最早什么时间能从a地到b地。注意一条换乘线路的时间是线路上最后一段火车的到达时间。

输入格式

第一行三个整数n,m,q

接下来m行,每行三个整数ai,bi,ci

最后q行,每行表示一个询问ai,bi, aibi

输出格式

q行,每行一个整数表示答案。

如果不能到达输出-1.

样例一

input

3 3 3
1 3 1
2 3 2
1 2 1
1 2
1 3
2 3

output

1
1
1

样例二

input

3 3 3
1 3 5
2 3 2
1 2 7
1 2
1 3
2 3

output

7
5
2

数据范围

时间限制1s, 空间范围512MB

q105

测试点编号 n的规模 m,ci的规模
1,2n20mn2,ci109
3,4n500mn2,ci109
5,6n3000m5×105,ci100
7,8,9,10n3000m5×105,ci109
#15. B

小w有一颗n个点的无根树,他想要把这棵树上的节点两两匹配起来,任何一个点只能在一对匹配中。

可是小w发现,无论怎么匹配,树上还是最多只能有a对匹配。

小w非常生气,他决定自己动手,往树上加一条边,使得树上有a+1对匹配。

请问小w有多少种加边的方案,可以达成自己的目标呢?

输入格式

第一行一个整数n,表示树的点数。

接下来n1行,每行两个整数ab,表示树的一条边(a,b)

输出格式

样例一

input

6 
1 2 
1 3 
1 4 
1 5 
2 6

output

3

数据范围

时间限制 1s, 空间范围 512MB

测试点编号 n的规模
1,2n20
3,4n500
5,6n3000
7,8,9,10n200000
#16. T3

小w和小y互相暗恋了对方两年,本可以一直在一起,但是无奈命运和时机都一一错过,留下的只有一片回忆。

在小w的梦里,他和小y一起玩一场直到永远的游戏。游戏规则如下:

游戏的棋盘是一个梦幻的国度,这个国度有n座城池,每个城池不是归小w所有,就是归小y所有,城池和城池之间用m条有向边连接。

现在有一个遗失的记忆碎片降临到了城市s。每当碎片来到一座城市的时候,城市的主人就选择一条出边,把碎片沿着出边移动到对应的城市。保证每个城市至少有一个出边,不能不选。

小w和小y无穷无尽地玩着这个游戏。每个城池有一个属性pi,碎片的移动轨迹上所有城池的pi形成了一条无限长的属性数列。

现在如果数列的上极限是偶数,那么小w就取得了胜利,如果数列的上极限是奇数,那么小y就取得了胜利。

通俗来说,所谓的上极限,就是数列里最大的出现了无穷多次的数字。

输入格式

第一行一个T,表示数据组数。

每组数据第一行两个整数n,m

接下来n行,每行一个整数xi,pi.

xi=0表示这是小w的城池,反之xi=1则是小y的。pi表示第i个城池的属性。

接下来m行,每行两个整数ai,bi。表示一条从aibi的有向边。

输出格式

T行,每行n个字符,表示每个点出发谁获胜,"w"表示小w获胜,"y"表示小y获胜。

样例一

input

3
2 2
1 1
0 2
1 2
2 1
5 7
0 2
1 2
1 4
0 5
0 2
2 1
1 2
4 1
2 4
1 3
3 2
5 5
4 6
1 2
0 2
1 4
0 5
2 1
1 2
4 1
2 4
1 3
3 2

output

ww
yyyyw
wwww

数据范围

时间限制3s,空间限制512MB

T5

测试点编号 n,pi的规模
1,2n10,1pi7,mn2
3,4n20,1pi7,mn2
5,6n28,1pi7,mn2
7,8,9,10n50,1pi7,mn2
#17. A

Lyra 做了个梦,梦见自己身处一片蒲公英花田里,拥有魔法的自己可以让蒲公英们可以实现自己的愿望。每个蒲公英有三个属性si,pi,ti,对于第 i 株蒲公英,只有当 Lyra 的魔法值达到至少 si 的时候才有能力去完成这株蒲公英的愿望,当然需要花费她 ti 天的时间,完成愿望后蒲公英作为奖励,在随风飘散的同时还会帮助 Lyra 继续提升自己,Lyra 的魔法值会增加 pi(注意帮蒲公英实现愿望不需要消耗魔法值)。

Lyra 初始时拥有魔法值 R,她想知道 T 天之内她最多能获得多少魔法值,你只需要输出她最终的能力值和完成任务的顺序即可。

输入格式

第一行三个整数 n,T,R,意义如题所述。

接下来 n 行,每行三个整数表示 si,pi,ti

输出格式

第一行一个整数表示 T 天后 Lyra 的魔法值的最大值。

第二行若干个整数按次序给出 Lyra 依次完成愿望的蒲公英的编号。

样例输入输出

样例输入1

4 6 10
10 10 4
5 10 2
15 20 4
20 50 3

样例输出1

70
2 4

样例输入2

/dandelion/ex_dandelion2.in

样例输出2

/dandelion/ex_dandelion2.ans

样例输入3

/dandelion/ex_dandelion3.in

样例输出3

/dandelion/ex_dandelion3.ans

数据范围与约定

对于全部数据 1n1000;1ti,T1000;1si,R109;1pi106.

Subtask 1[17pts]:}

n9;ti,T100;si,R109;pi106.

Subtask 2[23pts]:}

n,T,R,si,pi,ti100.

Subtask 3[21pts]:}

ti=1.

Subtask 4[39pts]:}

No Special Constraints.

时间限制:1s

空间限制:666MB

下载

样例数据下载

#18. B

Lyra 是一个灵巧的女孩子,她特别喜欢玩一种叫“石头剪刀布”的游戏,在这个游戏中,每回合双方同时打出一种手势,为石头(r),剪刀(s),布(p)之一,规定石头打败剪刀,剪刀打败布,布打败石头,若手势一样则视为平局。

虽然 Lyra 是一个灵巧的女孩子,她发现她依然赢不了 Evan,潜心研究多日 Evan 的策略后,发现在第二天的 n 轮游戏中,Evan 一定以某种固定策略出手势。

这个固定策略(一个长度为 n 的由 r,s,p 组成的字符串)就藏在 Evan 的电脑里,被 Evan 加密存储。Evan 的加密方式很奇怪,他先选取一个特定的 d,然后把整个字符串循环右移 d 个位置。

Lyra 拿到了加密后的策略串,她想在第二天的石头剪刀布比赛中大败 Evan,注意 Lyra 的策略不一定必须是开始前固定的,可以根据前若干回合的结果修正之后的策略。

在这场石头剪刀布大赛中,对于第 i 个回合,获胜可以获得 wi 分,平局获得 di 分,而失败获得 0 分。Lyra 想知道自己采取最优策略的话,最坏情况下至少从这 n 个回合中获得多少分。

输入格式

第一行三个正整数 n 表示回合数。

第二行一个长度为 n 的字符串 S 表示 Evan 的序列的某个轮换。

接下来 n 行每行两个整数 wi,di,表示获胜得分,平局得分。

输出格式

一行一个正整数表示 Lyra 至少获得的分数。

样例输入输出

样例输入1

5
rrsrr
3 1
3 1
3 1
3 1
3 1

样例输出1

12

样例输入2

6
rsprsp
3 1
3 1
3 1
3 1
3 1
3 1

样例输出2

    15

样例输入3

/dexterity/ex_dexterity3.in

样例输出3

/dexterity/ex_dexterity3.ans

注意: 对于所有的样例数据,获胜收益为 3,平局收益为 1

数据范围与约定

对于全部数据 1n1×105;0diwi109.

Subtask 1[5pts]:

n10.

Subtask 2[14pts]:

n16.

Subtask 3[17pts]:

n50.

Subtask 4[18pts]:

n1000.

Subtask 5[19pts]:

n105;S 随机生成.

Subtask 6[27pts]:

n105.

时间限制:1s

空间限制:666MB

下载

样例数据下载

#19. C

Lyra 新进入了一家自动飞行公司开始了实习,作为一名同时精通算法,系统,硬件的天才,她刚入职了两周就设计了一种自动飞行蜻蜓的模型。与无限撞玻璃的普通昆虫不同,这种蜻蜓可以自动识别出房间的门并从中穿过。

Lyra 甚至宣称,这种蜻蜓还对路线有完整的把握,可以时时刻刻知道自己在哪并规划路径。

为了演示这种蜻蜓的飞行技术,Lyra 设计了 n 个房间,每个房间有左右两个门,两个门走出去都会进入一个单向通道,并从烟囱落入另一个房间,换言之,对于编号为 i[1,n] 的房间,有两个属性 Li,Ri[1,n],若从左边的门出去则会飞到第 Li 个房间,而若从右边的门出去则会飞到第 Ri 个房间(注意 L,R 不一定是排列)。

虽然房间系统非常复杂,Lyra 宣称她的电子蜻蜓依然可以在穿过错综复杂的通道系统后回到自己的房间,可就在 Demo 前一天,Lyra 还没有开始写位置记录系统,情急之下 Lyra 决定让蜻蜓按照如下的方法飞行:

重复 A 次:走左边的门;

再走右边的门;

再重复 B 次:走左边的门;

再走右边的门;

再重复 C 次:走左边的门。

Lyra 发现只要自己精心设计房间的通道系统(即 Li,Ri),电子蜻蜓无论从哪个房间出发,经过这一系列操作后都会回到原来的房间,这样就能混过 Demo 了。

Lyra 还很好奇一共有多少种不同的通道系统可以做到这样呢?两种系统被认为不同当且仅当存在 i 使得对应的 LiRi 不同。

输入格式

第一行一个整数 T 表示数据组数。

接下来 T 行 每行四个整数 n,A,B,C,意义如题所述。

输出格式

对于每个输入输出一行一个整数表示答案对 998244353 取模的结果。

样例输入输出

样例输入1

3
3 1 1 1
5 2 3 4
20 13 18 100

样例输出1

6
600
17287547

样例解释1

对于第一组数据,可行的六种方案是:

L={1,2,3},R={1,2,3}

L={1,2,3},R={1,3,2}

L={1,2,3},R={2,1,3}

L={1,2,3},R={3,2,1}

L={2,3,1},R={1,2,3}

L={3,1,2},R={1,2,3}

数据范围及约定

对于 5% 的数据,n5;

对于 15% 的数据,n8;

对于 25% 的数据,n10;

对于 35% 的数据,n20;

对于 55% 的数据,n50;

对于 75% 的数据,n400;

对于 100% 的数据 1T10;1n1000;0A,B,C1018.

时间限制:2s

空间限制:666MB

下载

样例数据下载

#20. A

本题是交互题,仅支持C++语言。

Lyra 和 Evan 喜欢周游世界,有时他们会向对方炫耀自己去过哪些国家,和在这些国家的见闻。一般来说这是令人愉悦的交谈,但为了凸显自己经历的丰富,Lyra 和 Evan 在描述时会带上夸张的成分,这就导致了,如果他们恰巧去过同一个国家,会因为维护自己吹得牛哔而吵起来……

Lyra 喜欢百花齐放,不收沾染的地域文化,而 Evan 着眼于文化之间密切的交流,所以 Lyra 访问的国家,没有任何一对国家间有航线链接,而 Evan 访问的国家,任意一对国家都有航线直接可达。 更为令人费解的是, 无论是 Lyra 还是 Evan,关于自己去过哪些国家,在其他人面前都守口如瓶。在热衷于八卦的你百般打听之下,他们决定用告诉他们去过的国家的编号——当然这编号是他们自己造的,而你跟不知道编号是怎么对应的。

然而,热衷于八卦的你才对 Lyra 和 Evan 去过哪些国家不感兴趣,你只关心他们会不会吵起来,你连忙比较 Lyra 和 Evan 告诉你去过的国家的编号集合,却发现,Lyra 和 Evan 使用的根本就是两套编号系统。

Lyra 和 Evan 决定告诉你不超过 K 对编号之间的对应关系,而你想从这消息中判断他们是否会吵架。

出于好心,Evan 和 Lyra会各给你一份航线图,当然国家是用他们自己的方式编号的,编号都从 1n,但两人的编号方式并不相同。

交互说明

你需要在文件中包含 effulgence.h,即在文件头部写上:#include "effulgence.h"

你需要编写一个函数:

bool QuarrelOrNot(int n, std::vector lyra_set, std::vector evan_set);

其中 n 表示国家的数目,lyra\_setevan\_set 分别表示两人访问过得国家的集合(自己的编号系统中,没有重复),你可以调用一些函数来获取两张航线图,再询问一些顶点之间的对对应关系。

你的函数可以使用以下函数:

std::pair GetNextFlightFromLyra(); 会返回一个 std::pair 表示一条 Lyra 地图上的双向航线,当返回 (0,0) 时,说明 Lyra 地图上的航线已添加完毕。

std::pair GetNextFlightFromEvan(); 会返回一个 std::pair 表示一条 Evan 地图上的双向航线,当返回 (0,0) 时,说明 Evan 地图上的航线已添加完毕。

int FromLyraToEvan(int id); 会返回一个整数表示在 Lyra 的地图上编号为 id 的国家在 Evan 的地图上的编号。

int FromEvanToLyra(int id); 会返回一个整数表示在 Evan 的地图上编号为 id 的国家在 Lyra 的地图上的编号。

注意你的程序只有接收完毕 Lyra 和 Evan 地图上的所有航线才可以调用询问对应关系的两个函数,否则会被判错误。

你的程序可以在任意时刻返回一个答案, true 表示两个人访问过同一个国家,而 false 表示两个人访问的国家集合不相交。

数据不会有重边和子环。在一张地图上的航线已添加完毕之后继续调用返回航线的函数会继续返回 (0,0)

交互库输入格式

第一行四个正整数 n,m,nL,nE,表示国家数,双向航线数,Lyra 访问过得国家数,Evan 访问过的国家数。

第二行 n 个整数为一个排列 pi 表示 Lyra 地图上编号 i 的国家在 Evan 的地图上编号为 pi

第三行 nL 个整数表示 Lyra 访问过的国家编号。

第四行 nE 个整数表示 Evan 访问过得国家编号,注意这里的编号是在原图上(即 Lyra 的编号系统)。

接下来 m 行,每行两个整数表示一条双向航线的两个端点。

交互库输出格式

若非正常结束交互库会输出错误信息。

当调用询问对应关系的函数超过 106 次后交互库会返回错误。

否则第一行会输出一个字符串 Correct! 表示正确 Wrong! 表示错误。

第二行输出一个数 K 表示你使用的询问次数,接下来 K 行每行描述你调用的询问对应关系的函数记录。

样例输入输出

样例输入1

4 5 2 3
1 2 3 4
1 3
2 3 4
1 2
2 3
3 4
4 1
2 4

样例输出1

Correct!
3
FromLyraToEvan(1) = 1
FromLyraToEvan(2) = 2
FromLyraToEvan(3) = 3

样例输入2

/effulgence/ex_effulgence2.in

样例输出2

/effulgence/ex_effulgence2.ans

数据范围与约定

对于全部数据 1n1000;1nL,nE1000;0mn(n1)2.

详细测试点和部分分信息如下表所示:

子任务 n 分值 30 要求 60 要求 100% 要求
1 15 20 K20 K10 K5
2 100 30 K50 K15 K8
3 1000 50 K40 K15 K10

提示: 数据中可能存在高度对称的图(即可能有指数级数目的不同映射),所以尽可能不要使用任何图同构近似算法。

如何测试你的程序

下发文件中有 grader.cppeffulgence.h,将你的源程序和这两个文件放在同一文件夹下并运行:

g++ -o effulgence grader.cpp effulgence.cpp -O2 --std=c++11

即可编译你的代码。

时间限制:2s

空间限制:666MB

下载

样例数据下载

#21. T2

Lyra 最近迷上了刺绣,由于对字母的执念,她只喜欢在布条上绣字符串,Lyra 认为字母的大小写是不一样的,所以每个位置她一共有 52 种图案的选择。

现在 Lyra 完成了一个长度为 n 的字符串并把它送给了 Evan,可是作为 OIer,Evan 只对 \sout{肥宅快乐串} 本质不同的子序列感兴趣。

于是 Evan 给了你 m 个询问,每次询问一个区间,你需要告诉 Evan 这个区间里有多少个本质不同的子序列,当然这个子序列得非空。

字符串 S[1,|S|] 的一个子序列定义为一个序列 Si1Si2Sim 其中 1i1i2imm 为子序列的长度。

本质不同的子序列表示把子序列看成字符串并去重的结果,例如 lzz 的本质不同的子序列有 l,z,lz,zz,lzz

当然本质不同的子序列数目可能很多,你只需要对质数 P 取模即可。

输入格式

第一行四个整数 n,m,P,tpn,m,P 意义如题所述,tp=0 表示询问从输入读入,而 tp=1 表示询问由伪随机生成。

第二行一个长度为 n 的由大小写字母组成的字符串。

tp=0,接下来 m 行,每行两个整数 li,ri 表示每个询问的询问区间。

tp=1,接下来一行五个整数 x,y,a,b,c,询问生成方式如下:

D=109+7,u0=x,v0=y

ui=((aui1+bvi1+ci) XOR ansi1)modD

vi=((bui1+cvi1+ai) XOR ansi1)modD

li=min((uimodn)+1,(vimodn)+1)

ri=max((uimodn)+1,(vimodn)+1)

[li,ri] 即为第 i 个询问的区间。

其中 XOR 表示按位异或运算,ansj 表示第 j 个询问的答案,规定 ans0=0,注意这里的 ansj 是已经对 P 取过模的结果。

输出格式

为简化输出,对 tp=0 你需要输出所有询问答案的异或和,而对于 tp=1,你只需要输出 ansm 即可。

样例输入输出

样例输入1

3 3 1009 0
Lzz
1 2
2 3
1 3

样例输出1

4

样例解释1

三个询问的答案分别是 3,2,5,异或和是 4

样例输入2

/embroidery/ex_embroidery2.in

样例输出2

/embroidery/ex_embroidery2.ans

数据范围及约定

对于全部数据 1n,m106;108P109+7 是质数;0<x,y,a,b,c<109+7;1lirin.

S 为字符串中出现的不同的字符数目,各个测试点限制如下表所述:

测试点编号 n m S tp 测试点编号 n m S tp
1 15 100 26 0 11 100000 1 10 0
2 20 1 12 52
3 1000 1000 2 13 1000000 1000000 20 1
4 10 0 14 20
5 30 1 15 40
6 52 16 40
7 50000 50000 3 17 52
8 10 0 18
9 100000 100000 3 19
10 10 1 20

时间限制:2s

空间限制:666MB

下载

样例数据下载

#22. C

Lyra 对图的对称性很有研究,她格外喜欢一类对称性很强的图,记为 Dk,其中 k 是一个非负整数,Dk 是一个有 2k 个节点的图,若把节点编号为 02k1,则两个节点之间连边当且仅当两个节点的编号的异或是某 2 的次幂。

Lyra 还特别喜欢研究图的乘积,记 G1=(V1,E1),G2=(V2,E2),则 G1×G2 定义为

(V1×V2,{((u1,u2),(v1,v2))(G1×G2)2|u1=v1(u2,v2)E2u2=v2(u1,v1)E1})

即对点做笛卡尔积后,两个新点之间连边当前仅当其中一个点在对应原图中相同,另一个点在原图中有直接连边。

Lyra 曾经有一个 Evan 送给她的无向图 G 可惜她把这个图弄丢了,现在 Lyra 只能通过以前的实验数据来推测 G

Lyra 有一个图 H,且已知其同构于 G×Dk,并且可以假设不存在任何大于零的整数 k1 和无向图 G1 使得 G1×Dk1 同构与 G

Lyra 想请你还原出 G 并向她证明这确实是一个可行的 G,为此,你要找出可行的 k 并对 H 进行重标号。

输入格式

第一行两个整数 n,m 表示点数和边树。

接下来 m 行每行两个整数 u,v 表示一条无向边。

输出格式

第一行输出一个整数 k 表示找到的 k

接下来 n 行,每行一个整数 ti 和一个长度为 k01si

要求:

每个 [1,n2k] 内的整数都要在 ti 中出现恰好 2k 次。

每个长度为 k01 串要在 si 中出现恰好 n2k 次。

(ti,si) 有序对不存在重复。

存在一个点数 n2k 的图 G=([1,n2k],E),对于任意两个点 u,vu,v 之间有边当且仅当 (tu,tv)Esu=svtu=tvsusv=2p。(p 为任意非负整数, 表示异或)。

样例输入输出

样例输入1

4 4
1 2
3 4
1 4
2 3
####样例输出1
2
1 00
1 01
1 11
1 10

样例输入2

6 9
1 2
2 3
3 1
4 5
5 6
6 4
1 4
2 5
3 6

样例输出2

1
1 0
2 0
3 0
1 1
2 1
3 1

样例输入3

/equipoise/ex_equipoise3.in

样例输出3

/equipoise/ex_equipoise3.ans

数据范围及约定

对于全部数据 1n,m2×105.

K 表示答案中可行的 k

Subtask 1[9pts]:}

n20.

Subtask 2[13pts]:}

n100.

Subtask 3[10pts]:}

n=2K1000.

Subtask 4[25pts]:}

n1000.

Subtask 5[10pts]:}

n=2K105.

Subtask 6[33pts]:}

n105.

时间限制:1s

空间限制:666MB

下载

样例数据下载

#23. A

题目描述

小w想要解决一个有关整数的问题。

给定n,他想要知道k=1ni=1kj=1kgcd(i,j,k)对质数mod取模的值。

输入格式

从标准输入读入数据。

输入第一行包含两个正整数 n,mod

输出格式

输出到标准输出。

输出一行一个整数,表示答案对mod取模的值。

样例

输入

50 998244353

输出

58514

子任务

对于30%的数据,n100

对于60%的数据,n107

对于100%的数据,n109

时间限制:1s

空间限制:512MB

下载

样例数据下载

#24. B

题目描述

小h想要给蚯蚓安家。

蚯蚓的家园是一棵n个点的树。点从1n标号。一共有m条蚯蚓。每条蚯蚓的家在树上的某个点上,蚯蚓的家可以重叠。

但是小h有q个限制。

q个限制分别为第ai个蚯蚓的家和第bi个蚯蚓的家在树上的任何一条路径都经过了点ci

小h发现他并不会处理这些麻烦的限制,所以他向你求助。数据保证一定有解。

输入格式

从标准输入读入数据。

第一行三个正整数n,m,q

接下来n1行,每行两个正整数x,y,表示树上的一条边。

接下来q行,每行三个正整数ai,bi,ci,意义如题面所示。

数据保证有解。

输出格式

输出到标准输出。

一行m个正整数,其中第i个表示第i个蚯蚓的家所在的地方。

样例

输入

2 2 1
1 2
1 2 1

输出

1 1

子任务

对于20%的数据,n,m,q5

对于40%的数据,n,m,q15

对于100%的数据,n,m250q5×104

时间限制:1s

空间限制:512MB

下载

样例数据下载

#25. C

题目描述

小x在搭积木。

她的积木有nm列。

小x迷迷糊糊的,所以他只记得自己的积木从正面看和从侧面看的样子。

现在,小x想要知道有多少种方案符合他的观察。

输入格式

从标准输入读入数据。

第一行两个正整数n,m

接下来一行n个整数,表示小x正面观察到的高度。

接下来一行m个整数,表示小x侧面观察到的高度。

输出格式

输出到标准输出。

一行1个正整数,表示不同的方案对109+9取模的值。

样例

输入

4 5
5 2 4 1
5 2 4 0 1

输出

429287

子任务

对于20%的数据,n,m10

对于40%的数据,n,m50

对于100%的数据,n,m200

时间限制:1s

空间限制:512MB

下载

样例数据下载

#26. T1

题目描述

小w在玩一个游戏。

给定一个长度为n的序列。其中第i个数是ai

小w会玩两轮游戏。

每一轮,他都会拿出这个序列的某个非空区间。他需要保证这两轮拿出的区间严格不相交,并且第一轮拿出的区间在第二轮区间的左边。

小w得到的收益是这两个区间的区间最小值。

现在,小w想要知道。所有可能的游戏情况的收益和多少。

答案对109+7取模。

输入格式

从标准输入读入数据。

输入第一行包含一个正整数 n

接下来一行n个正整数,表示ai

输出格式

输出到标准输出。

输出一行一个整数,表示答案对109+7取模的值。

样例

输入

5
9 5 6 6 5

输出

179

子任务

对于20%的数据,n50

对于40%的数据,n300

对于60%的数据,n3000

对于100%的数据,n2×105,1ai109

时间限制:1s

空间限制:512MB

下载

样例数据下载

#27. B

题目描述

小h在种蔬菜。

作为一位理论计算机科学家,小h对于种菜有一套独特的理解。

小h打算在接下来的n天里每天在心里随机一个[0,Q]之间的随机数。如果这个数>0,那么他就会去田里劳动。假设这是他第i次劳动,他的心情就会变好ik

现在小h想要知道他的心情期望变好多少呢?

请输出这个期望乘上(Q+1)n的值,答案对109+7取模。

输入格式

从标准输入读入数据。

一行三个正整数n,k,Q,意义如题面所示。

输出格式

输出到标准输出。

一行一个整数,表示答案对109+7取模的值。

样例

输入

2 2 2

输出

24

子任务

1n109,1Q109,0k3×103

对于10%的数据 : n2

对于另外20%的数据 : n20

对于另外10%的数据 : k=0

对于另外20%的数据 : n106

对于100%的数据 : 无特殊性质。

时间限制:1s

空间限制:512MB

下载

样例数据下载

#28. C

题目描述

维护一个小写字母的字符串vector S,支持操作:

输入格式

从标准输入读入数据。

输入共 M+1 行。

第一行两个非负整数 M, T,表示操作次数及是否需要强制在线。

接下来 M 行,每行表示一个操作,格式如题目描述所示。

为了强制在线,当 T=1 时,若输入的整数为 a,则真实的输入数据为a xor lastans。输入的字符串由小写字母构成,若输入的小写字母在字母表中是第 b 个,真实的小写字母在字母表中是第 (b+lastans)mod26+1 个。其中lastans 表示上一次询问的答案,初始 lastans=0

输出格式

输出到标准输出。

对于每个 Q 操作,输出一行表示答案。

样例

输入

5 0
I 0 orzfsf
I 1 fsforz
Q 1 2 fsf
I 0 orz
Q 1 3 orz

输出

2
3

子任务

LM 为修改串的总长度,LQ 为询问串的总长度。

对于所有数据,1MMmax,1LM3M,1LQ2M,解密后 k, l, r 的值均保证合法。

对于测试点 1,在所有 I 操作都进行完后才会出现 Q 操作。

测试点编号 T Mmax 此部分分值 时限
1 0 40000 10 4S
2 0 40000 20 4S
3 1 40000 20 4S
4 1 40000 20 4S
5 1 100000 30 9S

空间限制:1024MB

下载

样例数据下载

#29. New Problem

kpkdopkopspodujnkouidjs读入一个整数 n,表示题目中提到的 3 位大爷 AC 的总题数。请输出他们分别 AC 的总题数。如果你不能正确读入,那么将获得 0 分。前 3 个测试点你正确读入即可获得 6 分,第 4 个测试点你正确读入只能获得 3 分。如果你不会做这道题,请直接输出 “WOBUHUI

下面有一个样例:

233

ksdfsdf
#30. candy

糖果

题目描述

一天,小 D 决定买一些糖果。他决定在两家不同的商店中买糖果,来体验更多的口味。

在每家商店中都有 n 颗糖果,每颗糖果都有一个权值:愉悦度,代表小 D 觉得这种糖果有多好吃。其中,第一家商店中的第 i 颗糖果的愉悦度为 Ai,而第二家商店中的第 i 颗糖果的愉悦度为 Bi

在每家商店买的糖果会被打包到一个袋子中(可以在一家商店什么都不买,此时认为这家商店的袋子为空)。小 D 回家后,因为这两个袋子外观是一样的,所以他会从两个袋子中随机选择一个.,然后吃光里面的糖果。小