清华集训Day3=。=

=。=妖兽啦,清华集训出模板题啦

于是由于雪舞喵昨天说过的太困了,导致今天早上忘带笔了,然后调了3个小时的模板都没调出来,最后只得了10分=。=

真是惨啊,那么今天就不贴代码了=。=

说起来今天也算发生了小小的出题事故,T2劼标程被艹了,T3由于题意等原因引发了一系列吐槽=。=

T1 石家庄的工人阶级队伍比较坚强

时间限制: 2.0 秒 内存限制: 512 MB

【问题背景】

B君和G君在过街天桥上。

B君:「又到冬天啦,算起来到大学已经三年多了」

G君:「是呀」

B君:「街上的情侣又多起来了,想想三年之前,我也是这样……」

G君:「??」

B君:「……在天桥上看情侣的!」

G君:「唔。」

B君:「不过这次有你陪我了呢~」

G君:「……」

B君:「诶诶,我有个问题想问你~」

G君:「问吧」

B君:「假设 \(n=3^m\) 个人一起玩cei ding ke」

G君:「啊咧?cei ding ke 是什么?」

B君:「就是石头剪刀布~,我们也叫钉杠锤」

G君:「你就问这个?」

B君:「你等会,我还没说完呢」

【问题描述】

\(n = 3^m\) 个人在玩石头剪刀布, 一共有 \(t\)  游戏,每轮有 \(m\)  石头剪刀布。

在同一轮的 \(m\) 次游戏中,每个人的决策必须是提前确定的,也就是说不能采用随机策略,也不能根据前若干局的结果决定下一局的决策; 这样,显然一共有 \(n = 3^m\) 种决策。

\(n = 3^m\) 个人会采取两两不同的决策。 为了方便表达,对于第 \(x\)\(0 \leq x < n\) )个人,将 \(x\) 转换成三进制得到一个 \(m\) 位的数。 其中 \(0\) 表示剪刀, \(1\) 表示石头, \(2\) 表示布。就得到了第 \(x\) 个人采取的策略。

由于编号是固定的,因此每个人在不同轮的 \(m\) 次游戏中都会采取同一套决策。

\(x\) 个人在最初时有一个分数 \(f_{0, x}\)

在第 \(i\) 轮中,他将和另一个人 \(y\) 进行 \(m\) 次的石头剪刀布的比赛。

我们用 \(W \left( x, y \right)\) 表示 \(x\) 在和 \(y\)\(m\) 次比赛中赢的次数; 用 \(L \left( x, y \right)\) 表示 \(x\) 在和 \(y\)\(m\) 次比赛中输的次数。

在第 \(i\) 轮结束之后,第 \(x\) 个人分数是:

\[ f_{i, x} = \sum_{0 \leq y < n} f_{i-1, y} b_{u, v}\]

其中 \(u = W \left( x, y \right) = L \left( y, x \right), v = L \left( x, y \right) = W \left( y, x \right)\) ,平局不计入次数; \(b_{u,v}\) 则是一个给定的评分数组。

注意即使 \(y\)\(x\) 一样(自己转移到自己)也会乘上一个系数 \(b_{0, 0}\) (即自己跟自己打全为平局)。

显然随着轮数越来越多,分数也会越来越大, 这个计分系统和我们平时用的计算机一样,也会溢出。 当要储存的分数 \(f\) 大于等于 \(p\) 的时候,就会变成 \(f \bmod p\)

B君想知道 \(t\) 轮之后所有人的分数,也就是 \(f_{t, 0}, f_{t, 1}, \ldots, f_{t, n - 1}\)

G君:「诶,我发现这个数 \(p\) 有特殊的性质诶!不存在两个正整数,使得他们倒数的和等于 \(3/p\) !」

B君:「G君好棒!不过这个题怎么做呢?」

【输入格式】

从标准输入读入数据。

第一行三个整数,表示 \(m, t, p\) 。保证 \(0 \leq m \leq 12\)\(0 \leq t \leq 1000000000\)\(1 \leq p \leq 1000000000\)

第二行有 \(n = 3^m\) 个整数,表示 \(f_{0, 0}, f_{0, 1}, \ldots, f_{0, n - 1}\) 。保证 \(0 \leq f_{0, i} < p\)

接下来的部分是一个数组 \(b\) ,第 \(1\)\(m + 1\) 个数,第 \(2\)\(m\) 个数……第 \(m + 1\)\(1\) 个数。

其中第 \(i\) 行的第 \(j\) 个数为 \(b_{i-1, j-1}\)\(i, j \ge 1, i + j - 2 \le m\) ),保证 \(0 \leq b_{i, j} < p\)

不存在两个正整数,使得他们倒数的和等于 \(3/p\) 。 即不存在正整数 \(x, y > 0\) ,使得 \(1/x + 1/y = 3/p\)

【输出格式】

输出到标准输出。

输出 \(n = 3^m\) 行,每行一个整数,表示每个人最终的得分。

其中第 \(i\) 行表示第 \(i\) 个人的得分 \(f_{t, i}\)

【样例1】

输入

1 1 10009

10 100 1000

2 3

4

输出

4320

3240

2430

【样例2】

输入

2 3 103

7 8 9 10 11 12 13 14 15

1 2 3

4 5

6

输出

96

8

73

38

53

15

27

42

4

【子任务】

测试点 m t p
1 = 3 \(\leq 10^{3}\) 无特殊性质
2 = 4
3 = 3 \(\leq 10^{9}\)
4 = 4
5 = 5
6
7 = 6
8 = 7
9 = 9 \(\leq 7\)
10 = 10
11 = 11
12 = 12
13 = 9 是质数
14 = 10
15 = 11
16 = 12
17 = 9 无特殊性质
18 = 10
19 = 11
20 = 12

于是今天这道题大概是唯一一道比较正常的题=。=然而标算是3进制的FWT,完全不会FWT的雪舞喵要是做了的话也只能打个 \(O(n^3\log t)\) 的暴力矩阵乘法……

至于p那个奇奇怪怪的性质好像是用来求单位根的……


你的生命已如风中残烛

时间限制: 2.0 秒 内存限制: 256 MB

【问题描述】

期中考试考完了,已经感到没有什么好害怕的六花今天决定不学数学了,于是和勇太打起了游戏王。

你已空手空场,生命只剩一百,事到如今你还能做什么?

所累哇多卡纳!

纳尼?

然而六花的卡组实在是太菜了,经过分析,六花发现在一回合内,她卡组中的牌并没有办法达成 OTK,除非主角光环附体:

被封印的艾克佐迪亚

[图片]

——包括这张卡在内,「被封印者的右足」「被封印者的左足」「被封印者的右腕」「被封印者的左腕」全在手牌的时候,获得决斗胜利。

但是因为六花不是高贵的氪金玩家,她可以肯定,这五张牌中肯定有一张,在牌堆的底端。所以六花现在面临着一个难题:需要在一回合内将卡组抽完。

六花的牌堆一共有 \(m+1\) 张牌,因为最后一张牌是固定的,所以我们现在只考虑前 \(m\) 张牌。

在这 \(m\) 张牌中,有 \(n\) 张特殊牌和 \(m-n\) 张普通牌,每一个特殊牌有一个属性值 \(w_i\) ,表示在打出这张牌后,可以再摸 \(w_i\) 张牌。幸运的是,六花发现这些牌刚好满足 \(\sum_{i=1}^n w_i=m\) ,因此她可以放心的随意摸牌而不用担心爆牌。

因为这 \(m\) 张牌是被打乱的,所以总共有 \( m! \) 种不同的可能的牌堆。

现在这回合开始了,六花先从牌堆里抽出一张牌,接着六花不断的打出手中的牌,如果打出特殊牌,则又可以摸牌,直到摸到最后一张牌达成胜利条件或者打光自己的手牌结束自己的回合继而输掉比赛。

举例来说,如果牌堆是 \({4,0,0,2,0,0,0}\) (用 \(0\) 表示普通牌,其他数字表示 \(w_i\) ,其中最后一个 \(0\) 是最后一个部件),那么六花打牌的过程可以为:

  1. 取一张牌,手中的牌为 \({4}\)
  2. 打出 \({4}\) ,再取四张牌,手中的牌为 \({0,0,2,0}\)
  3. 打出 \({2}\) ,还需要再取两张,这时已摸到最后一个部件,六花胜利。

而如果牌堆是 \({2,0,0,4,0,0,0}\) ,不难发现是勇太的胜利。

现在,六花想要知道这 \( m! \) 种不同的牌堆中,有多少种能够让她胜利。

【输入格式】

从标准输入读入数据。

第一行一个整数 \(n\)

第二行 \(n\) 个空格隔开的正整数 \(w_i\)

通过输入你可以自己算出来 \(m=\sum_{i=1}^n w_i\)

【输出格式】

输出到标准输出。

输出一个整数表示答案,答案可能很大,你只需要输出对 \(998244353\) 取模后的结果。

【样例1】

输入

15

输出

24

说明

所有可能的 \( m! \) 种牌堆中,只有形如 \({5,0,0,0,0,0}\)\(24\) 个牌堆满足条件。

【样例2】

输入

61 2 3 4 5 6

输出

90337303

【样例3】

下载目录下的 ex_card3.in 与 ex_card3.ans

【样例4】

下载目录下的 ex_card4.in 与 ex_card4.ans

限制与约定

对于 \(10\%\) 的数据, \(m \leq 10\)

对于 \(30\%\) 的数据, \(n \leq 8\)

对于 \(50\%\) 的数据, \(n \leq 15\)

对于 \(70\%\) 的数据, \(n \leq 30\)

对于 \(100\%\) 的数据, \(n \leq 40\)\(1 \leq w_i \leq 10^5\)

同时保证有 \(m-n \geq 4\) ,因为牌堆里毕竟要有这 \(5\) 个部件嘛。

这道题劼的标程是个n多少次方的dp,结果被yjq打表找规律暴力艹过去了……

答案就是 \(\frac{m!}{m-n+1}\)

………………

好像在最后剩5min的时候雪舞喵快速的敲了一个枚举全排列得到了10分……

接下来是我们的模板题!


温暖会指引我们前行

时间限制: 2.0 秒 内存限制: 512 MB

【问题背景】

寒冬又一次肆虐了北国大地

无情的北风穿透了人们御寒的衣物

可怜虫们在冬夜中发出无助的哀嚎

“冻死宝宝了!”

这时

远处的天边出现了一位火焰之神

“我将赐予你们温暖和希望!”

只见他的身体中喷射出火焰之力

通过坚固的钢铁,传遍了千家万户

这时,只听见人们欢呼

“暖气来啦!”

【问题描述】

虽然小R住的宿舍楼早已来了暖气,但是由于某些原因,宿舍楼中的某些窗户仍然开着(例如厕所的窗户),这就使得宿舍楼中有一些路上的温度还是很低。

小R的宿舍楼中有 \(n\) 个地点和一些路,一条路连接了两个地点,小R可以通过这条路从其中任意一个地点到达另外一个地点。但在刚开始,小R还不熟悉宿舍楼中的任何一条路,所以他会慢慢地发现这些路,他在发现一条路时还会知道这条路的温度和长度。每条路的温度都是互不相同的。

小R需要在宿舍楼中活动,每次他都需要从一个地点到达另一个地点。小R希望每次活动时经过一条最温暖的路径,最温暖的路径的定义为,将路径上各条路的温度从小到大排序后"字典序"最大。即温度最低的路温度尽量高,在满足该条件的情况下,温度第二低的路温度尽量高,以此类推(如果路径A是路径B的前缀那么将选择路径A)*。小R不会经过重复的路(不会重复经过某个地点)*。由于每条路的温度互不相同,因此只存在一条最温暖的路径。

对于小R的每次活动,你需要求出小R需要走过的路径总长度。如果小R通过当前发现的路不能完成这次活动,则输出-1。

*括号中内容原题并没有,因此导致题意不清晰,雪舞喵稍微修改一下

【输入格式】

从标准输入读入数据。

第一行两个正整数 \(n,m\) 。表示小R的宿舍楼中有 \(n\) 个地点,共发生了 \(m\) 个事件。

接下来 \(m\) 行,每行描述一个事件,事件分为三类。

  1. find id u v t l 表示小R发现了一条连接u和v之间的路,编号为id。相同id的边只会出现一次。 \((0\le id\lt m, 0\le u,v \lt n, u\ne v,0\le t\le 1000000000, 0 \lt l \le 10000)\)
  2. move u v 表示小R要从u到达v,你需要计算出最温暖的路径的长度 ,若不能从u到达v,则输出-1。 \((0\le u,v \lt n)\)
  3. change id l 表示从u到v这条边的长度变为了l(保证在当前时间点这条边存在)。 \((0 \lt l \le 10000)\)

【输出格式】

输出到标准输出。

对于每个询问,输出一行整数,表示最温暖的路径长度。

【样例1】

输入

8 19
find 0 0 2 7 2
find 1 2 4 4 4
find 2 4 6 10 1
find 3 6 7 8 6
move 2 7
move 1 6
find 4 2 5 3 4
move 0 5
change 0 12
find 5 4 5 5 10
find 6 2 3 6 9
move 3 5
find 7 0 1 12 1
move 1 6
find 8 1 7 11 100
move 1 6
move 3 7
move 5 6
move 2 2

输出

11
-1
6
23
18
106
122
11
0

【样例2】

输入

15 45
find 0 1 0 8 5987
find 1 2 0 14 5455
find 2 3 0 27 8830
find 3 4 3 42 7688
find 4 5 0 25 1756
find 5 6 5 35 1550
find 6 7 4 43 9440
move 3 9
change 2 9113
move 10 13
move 3 3
move 11 10
find 7 8 7 6 7347
find 8 9 8 26 8935
move 8 4
change 3 4466
find 9 10 9 28 8560
move 6 5
find 10 11 10 31 6205
change 9 9228
find 11 12 10 23 948
find 12 13 12 45 5945
move 0 9
move 2 5
change 2 6118
find 13 14 13 12 6906
move 4 1
change 2 504
find 14 4 2 22 9796
move 10 7
move 1 14
move 13 3
find 15 12 9 39 8985
find 16 9 8 17 3710
change 1 5370
find 17 1 0 36 4669
find 18 7 6 37 8087
move 9 0
find 19 14 9 33 8234
find 20 0 4 24 5209
change 1 4883
find 21 6 3 9 2461
find 22 5 2 19 4291
change 1 7219
change 6 4846

输出

-1
-1
0
-1
16787
1550
39301
7211
16571
25510
59706
46309
30692

【样例3】

下载目录下的 ex_move3.in 与 ex_move3.ans

【限制与约定】

对于100%的数据, \(1\le n\le 100000, 1\le m \le 300000\)

本题共有20个数据点,每个数据点5分。

测试点 \(n\) \(m\) 其它
\(1-2\) \(\leq20\) \(\leq50\) 无特殊约定
\(3-5\) \(\leq1000\) \(\leq3000\)
\(6-10\) \(\leq100000\) \(\leq300000\) 所有的find事件都在move事件之前,且没有change事件
\(11-14\) 所有的find事件都在move事件之前
\(15-20\) 无特殊约定

=。=这一看就是个lct的模板啊!维护个最大生成树就行了。出题人ryz说看这题名字,就是给大家送温暖的……

然而这个温暖雪舞喵并没有get到……0.5h就写出来了调了3h依然没过……

于是今天的雪舞喵太蒻了并没有代码

12.06.2016

Yukimai

(^=。=^)

发表评论