清华集训Day2=。=

雪舞喵好困啊=。=好困啊……

于是今天是清华集训Day2,由于t2是道题答,雪舞喵玩了3h的提答,然后随手写了个t1和t3的暴力=。=

结果t2用checker测了80多分,最后由于一些sb的问题和模数被卡了一个挂到了60多,导致雪舞喵今天连100分都不到=。=

那么先来粘题。

T1 如何优雅地求和

时间限制: 1.0 秒

内存限制: 512 MB

【问题描述】

π+e 在高中上数学课时经常睡觉,然而每次考试都能 AK,这让他的同桌叶子很是膜拜。

某天,老师在课上讲二项分布的题目:

(2010天津,18改)

某射手每次射击击中目标的概率p=1/3, 且各次射击的结果相互独立, 互不影响。

记4次中击中的次数为X, 求X的数学期望与期望的方差。

(答案:4/3,8/9)

老师说:“这个,二项分布的期望就是 np,方差就是 np(1−p),不信你们自己课后回去算。”

π+e 一听有附加题,马上打起了精神,三下五除二用了他的黑科技“母函数求导”就轻而易举的解决了这个问题。顺便帮叶子也给科普了一下。

2016年暑假的某天,π+e 突然想起了这件事。他想了想,把原来的问题加强了一下,变成下面这个样子:

有一个多项式函数 f(x),最高次幂为 x^m,定义变换 Q:

\[Q(f,n,x)=\sum_{k=0}^nf(k)\binom{n}{k}x^k(1-x)^{n-k}\]

现在给定函数 f 和 n,x,求 Q(f,n,x) mod 998244353。

然而,众所周知,高考考完是会掉很多智商的。π+e发现自己已经忘记掉怎么用的黑科技了;他打电话给叶子,叶子也说不记得了。

你能帮帮他吗?

出于某种原因,函数f由点值形式给出,即给定 a0,a1,⋯,am 共 m+1 个数,f(x)=ax。可以证明该函数唯一。

【输入格式】

从标准输入读入数据。

第一行三个整数 n,m,x,意义如前所述。

第二行共 m+1 个整数,表示 a0,a1,⋯,am。

【输出格式】

输出到标准输出。

输出一行一个数表示答案,请对 998,244,353 取模。

【样例1】

输入

4 1 332748118

0 1

输出

332748119

说明

注意到 \(332748118\equiv\frac{1}{3}(mod\, 998244353), 332748119\equiv\frac{4}{3}(mod\, 998244353), f(x)=x\) , 题目中所求的表达式为:

\[\sum_{k=0}^4k\binom{4}{k}(\frac{1}{3})^k(\frac{2}{3})^{4-k}=\frac{4}{3}\]

此即为题目开头二项分布例题计算期望的表达式。

【样例2】

输入

4 3 12

0 1 8 27

输出

46704

说明

经计算可得 \(f(x)=x^3\)

【样例3】

见下载目录下的 ex_sum3.in 与 ex_sum3.ans

【数据规模和约定】

对于所有的测试点,保证 \(1\le n \le 10^9, 1\le m\le 2*10^4, 0\le a_i,x < 998,244,353\)

测试点 n m 特殊限制
1 n≤100 m≤100 n=m
2 n≤1000 m≤1000
3 n≤10000 m≤1000 无约束
4 n≤1e5
5 n≤1e6
6 n≤1e9 m=1
7 m=2 \(f(x)=x^2\)
8 \(f(x)=x^2-x\)
9 m=3 无约束
10,11 m≤10
12,13,14 m≤100
15 m≤1000
16 m≤2,000
17 m≤4,000
18 m≤8,000
19 m≤12,000
20 m≤2e4

(这题myy15min怒A代码不足20行=。=)

又是一道在dalao们眼中很水的题=。=然而雪舞喵一向见数学题直接弃疗,而且今天还一直在玩提答……

然后就写了个10分的大暴力(题解原话:考察for循环的使用)

然后标算是把它搞成个下降幂的形式,然后把f函数差分一下啥的=。=

大概思路听懂了,然而雪舞喵肯定想不出来就是了=。=

T2 工厂

这是一道提交答案题

【题目描述】

跳蚤国作为一个发展中国家,生产力始终比发达国家跳晚国差一大截,因此发展生产力一直是跳蚤国第一重要的事。

近日,跳蚤国王在视察跳蚤国首都的X工厂时,发现这里的机器效率低下,而且污染严重,以至于跳蚤国首都几乎每天都是漫天雾霾……

X工厂是用来检验各地运来的产品的质量的。在X工厂的每个车间中,有若干个节点。每个节点有一台机器,这台机器对产品进行一些处理后,将其送给下一个节点。

跳蚤国王回忆起几个月前造计算机的经历,想到了一个绝佳的主意:使用高效、清洁的生物资源!于是在每个节点上,机器被换成了跳蚤。

具体来说:

  • 对于X工厂的每个车间,我们可以将所有节点从 11开始编号。
  • 对于每个产品,都有一个只由可见字符(即ASCII码在[32,126]区间内的字符)构成的字符串,作为其标识串。 在一开始的时候,产品被送到了第1 个节点上,然后这些节点需要检查该产品的标识串,最终接受(Accept)或拒绝(Reject)该产品。
  • 对于不同的车间,需要接受的产品的标识串集合是不同的。
  • 对于某个节点上的跳蚤,有trans和next两个属性。其中trans为一个大小为128的整数数组,next为一个整数。 当一个产品被送到这个节点上时,该产品的标识串的第一个字符将被移除,设其ASCII码为x, 则该产品在下一秒会被送到编号为trans[x]的节点上。 如果该产品的标识串已经是空串,则该产品下一秒会被送到编号为next的节点上。

蛐蛐国王对此表示十分支持,他派来了一些蛐蛐,来增加X工厂的处理能力。也就是说,一个节点上的跳蚤可以被替换成蛐蛐。

  • 每只蛐蛐有x和next两个整数属性。其中x的范围是[0,127]。
  • 当一个产品被送到这个蛐蛐节点上时,该产品的标识串的最后会被添加一个ASCII码为x的字符,然后该产品下一秒会被送到编号为next的节点上。

另外,对于任意一只跳蚤的trans或next,以及对于任意一只蛐蛐的next,其值可以等于0或者-1,其中0表示下一秒接受该产品,-1表示下一秒拒绝该产品。

由于跳蚤国资源的限制,一个车间最多能有300个节点。在处理一个产品的时候,最多只能花费1e6秒的时间。

跳蚤国王发现自己没有足够的能力来管理这么多跳蚤和蛐蛐,于是找到了参加清华集训的你。请你对X工厂的每个车间,确定需要使用的节点数n,以及每个节点使用的跳蚤或蛐蛐的属性。每个车间作为一个任务,要求如下:

任务1(5分)

接受所有1结尾的01作为标识串的产品。 如"111"是以1结尾的01串,而"110"和"233"都不是。 保证每个产品中,标识串的长度L满足1≤L≤100。

任务2(13分)

接受所有包含子串

aaaaaaaaaaaabaaaaaabaaaaaaaaaaaaaabaaabaaabaaaaaaaaaabaaaaaaaaabaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaorz

的串作为标识串的产品。 这个子串在该试题目录下的task2_string.txt中也存有一份。 保证每个产品中,标识串的长度L满足1≤L≤500000。

任务3(9分)

接受所有匹配的括号串作为标识串的产品。 匹配的括号串可以这么定义:

  • 空串是匹配的括号串
  • 如果S是匹配的括号串,则(S)是匹配的括号串
  • 如果X和Y都是匹配的括号串,则XY是匹配的括号串

如"(())()"是匹配的括号串,而"(()"不是。 一个等价的上下文无关文法为:

S -> SS | (S) | ε

保证每个产品中,标识串的长度L满足1≤L≤100。

任务4(12分)

接受所有匹配的括号串作为标识串的产品。 匹配的括号串的定义同任务3。 保证每个产品中,标识串的长度L满足1≤L≤900000。

任务5(6分)

接受所有从左到右看作为二进制数为3的倍数的01作为标识串的产品。 如(10010)2 = (18)10,所以一个标识串为"10010"的产品是可以接受的。 保证每个产品中,标识串的长度L满足1≤L≤100。

任务6(15分)

接受所有fib作为标识串的产品。 fib串可以这么定义:

  • 我们记f[1] = "a",f[2] = "b"
  • 对于i>2,我们定义f[i] = f[i - 1] + f[i - 2],其中+表示字符串的连接
  • 如f[3] = "ba",f[4] = "bab"
  • 那么,一个串s是fib串,当且仅当存在一个正整数i,使得s等于f[i]

如"bab"是一个fib串,而"baa"不是。 保证每个产品中,标识串的长度L满足1≤L≤400。

任务7(8分)

接受所有fib作为标识串的产品。 fib串的定义同任务6。 保证每个产品中,标识串的长度L满足1≤L≤200000。

任务8(14分)

接受所有表达式作为标识串的产品。 表达式可以这么定义:

  • 先引入另外一个定义:
  • 任何一个项都是一个表达式
  • "0"和"1"是项
  • 如果X是一个表达式,则(X)是一个项
  • 如果X和Y都是项,则X*Y是项
  • 如果X和Y都是表达式,则X+Y是表达式

如"(1+0)*1+0+(1)"是一个表达式,而"(1+1"不是。 一个等价的上下文无关文法为:

S -> S + T | T

T -> T * F | F

F -> 0 | 1 | (S)

保证每个产品中,标识串的长度L满足1≤L≤1000。

任务9(7分)

接受所有表达式作为标识串的产品。 表达式的定义同任务8。 保证每个产品中,标识串的长度L满足1≤L≤100000。

任务10(11分)

接受所有跳蚤语言的串作为标识串的产品。

  • 跳蚤语言为一种只有语句和控制结构的语言。
  • 为方便起见,跳蚤语言只由三种字符构成:'i'、'e'和'a'。
  • 其中'a'表示语句,'i'表示if,'e'表示else。
  • 一个跳蚤语言的串,可以是一个语句,或一个控制结构。
  • 语句即为"a",控制结构为"iAeB",或者是"iA",其中A可以是语句或控制结构,B也可以是语句或控制结构。
  • 对于一个'e',它总是会跟最近的一个'i'进行匹配。

如"iiaea"是一个跳蚤语言的串,因为它的后缀"iaea"作为一个控制结构整体,跟第一个"i"构成了一个"iA"型的控制结构。 如"iaeaea"就不是一个跳蚤语言的串,因为它最后一个"ea"找不到跟它匹配的"i"了。 如"iiaeaea"是一个跳蚤语言的串,并且第一个"ea"跟第二个"i"相匹配,第二个"ea"跟第一个"i"相匹配。

一个等价的上下文无关文法为:

S -> iSeS | iS | a其中e跟最近的i相匹配,即iSeS的优先级比iS要高。

保证每个产品中,标识串的长度L满足1≤L≤100。

【输入格式】

数据包中获取输入数据.

所有输入数据factory1.in ~ factory10.in分别对应10个任务。 每组输入数据仅包含一个整数,表示需要解决的任务编号。

【输出格式】

输出到标准输出。

输出文件为1.out ~ 10.out,分别对应相应的输入文件。 对于每组输入数据,你需要输出你使用的各个节点。 具体来说,第一行输出一个整数n,表示你使用了编号为1∼n的节点。 接下来nn行,按编号从小到大的顺序每行描述一个节点。 首先输出一个整数表示该节点的类型,其中跳蚤为1,蛐蛐为2。 对于跳蚤节点,先输出128个整数表示trans[0] ~ trans[127],再输出一个整数next。 对于蛐蛐节点,输出两个整数x和next。 要求trans[i]和next都在[-1,n]范围内,其中-1和0的意义见题目描述。 要求x在[0,127]范围内。 同一行中相邻两个整数用一个空格隔开。

在输出文件的最后,你可以添加任意内容,这不会影响你的得分。 我们建议你在此处写一些有意义的内容(如该任务的构造方法),以便于我们在考后进行统计分析。

【评分方式】

这道题没有部分分

我们提供了10个评分文件factory1.ans ~ factory10.ans,分别对应每个任务。

在每个评分文件中,第一行是一个整数m,表示有m组测试数据。接下来2m行,每两行表示一组测试数据,其中第一行为一个字符串,表示该测试数据的标识串,第二行一个字符串,为"Accept"(接受)或"Reject"(拒绝),表示该测试数据的答案。

本题中,我们对每个任务单独评分,每个任务的分值见题目描述。

如果你的输出格式不合法或者参数不符合题目约定,则得0分。

否则,按照以下规则来评分:

  • 首先测评器会从相应的评分文件中读取该任务的测试数据,并将每组数据代入你的输出。
  • 如果在代入某一组数据时,你处理该产品的时间超过了1e6秒,则得0分。
  • 如果在代入某一组数据时,你的输出与相应的答案不一样,则得0分。
  • 否则该任务得满分。

【如何测试你的输出】

在终端中先切换到该试题的目录下:(windows用户请使用cmd)

cd factory

我们提供checker这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是,先编译checker.cpp,假设编译后的文件名为checker,则在终端中运行

./checker <task_id>

其中task_id为任务的编号,例如

./checker 3

将测试3.out是否可以接受。(windows用户请使用checker 3) 在你调用这个程序之后,checker会根据你给出的输出文件给出测试结果。 另外,你可以直接不加参数运行checker,来测试这道题的所有输出文件。

我们还提供了一些其他的小工具,如用来运行/调试你的输出文件的工具,详细说明见该试题目录下的readme.txt。

注意:最终评测时,使用的评分文件factory1.ans ~ factory10.ans可能跟下发的不同。使用下发的评分文件测试的得分仅供参考。


于是雪舞喵今天把时间全砸在这题上了=。=这题松爷出的,然而数据好像比较水我的膜法骗过了两个点

题目给了一个方便的构造答案的头文件,还给了checker和simulator,而且题解里的图非常赞

于是subtask1只要建两个点,遇到0转移到1号点遇到1转移到2号点,接受2号点就可以了。

subtask2的话建个AC自动机=。=

subtask3搞一条链,遇到左括号前进一步遇到右括号后退一步,接受1号点就可以了=。=

(顺便一提应该建51个点雪舞喵只建了50个然后就被卡了)

然而subtask4上一个算法点数不够=。=

于是雪舞喵聪明的把一条链弄成了一个环,结果就被卡模数了(然而后面的subtask8和9都水过了)

标算大概是这样的,先弄一条链,从中间开始移动,遇到左括号向右移动,右括号向左移动,如果移动到头了就在新串中添加一个左/右括号并回到中点,然后递归处理新串,只接受中点。这样时间复杂度nlogn正好能卡过=。=

建新串就用蛐蛐节点在原串之后加字符就行了,用\0或者啥字符区分一下=。=

然而雪舞喵全程似乎忽略了蛐蛐(可以替换原串中的内容)的问题,一直想着构造DFA啊啥的,导致这个以及后面的点标算都没想出来=。=最后交上去的答案时间复杂度都是O(n)

subtask5的话雪舞喵觉得看起来很麻烦直接跳过弄后面的点去了,然而标算好像挺简单的,弄3个点代表%3=0,1,2就可以了。

subtask6雪舞喵使用了奇妙的算法,因为一个fib串是比他大的fib串的前缀,所以直接建一条链然后接受其中特定的点就可以了=。=

由于有一个串长度大于300了于是用一些奇妙的方法打个标记把它扔回去从头开始在匹配一下=。=

然而这个做法过不了subtask7。

标算好像是一直扫描这个串然后把ba替换成b,把b替换成a,然后最后剩个a就是正确的。

subtask8和9其实就是个括号匹配,雪舞喵使用了和subtask4一样奇妙的膜法然后就直接水过了,标算和subtask4类似。

subtask10的话标算好像是个n^2的不断把iaea和ia替换成a的方法=。=然而雪舞喵搞了个O(n)的奇妙算法(而且还是正确的),具体来说大概就是遇到i前进一步遇到e后退一步差不多,详见代码。

然后雪舞喵最后被卡成65。

T3 连通子树

时间限制: 5.0 秒 内存限制: 1024 MB

【问题描述】

小M至上主义者小D今天心情很好,准备给小M准备一个圣诞礼物。

他购买了一个圣诞树,这个圣诞树是一个有 n个点的树,点 i 有一个颜色 ci。小D觉得如果某种颜色太多就不好看了,所以最多会有 5 个点有相同的颜色。

小M收到了礼物很高兴,但是她最近对计数问题很感兴趣,于是她有一些问题想要小D解决。每次小M会关心三种不同的颜色 a,b,c,她想要知道这个圣诞树有多少个不同的非空联通子图满足里面颜色为 a,b,c 的点的个数分别为 na,nb,nc。由于数可能很大,输出关于对 1e9+7 取模的余数就可以了。

小D当然轻松解决了这个问题,你虽然被喂了狗粮,但你也想锻炼你的实力,你能解决这个问题吗?

【输入格式】

从标准输入读入数据。

第一行两个数 n 和 Q,表示树的大小和询问的个数。 第二行 n 个数,其中第 i 个表示 ci,为第 i 个节点的颜色。 接下来 n−1 行,每行两个数 a 和b,表示点 a 和点 b之间有一条边。 接下来 Q 行,其中每行有 6 个数 a,na,b,nb,c,nc,表示如题目中所述的询问。

【输出格式】

输出到标准输出。

对每个询问输出一行表示答案。

【样例】

【样例1】

输入

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

输出

3
1
2

【样例2】

输入

10 10
1 1 3 1 2 1 3 2 2 1
1 2
2 3
1 4
1 5
5 6
5 7
4 8
1 9
3 10
3 1 2 0 1 5
2 1 1 1 3 2
2 0 3 0 1 2
2 1 3 0 1 2
2 3 3 2 1 5
3 1 1 3 2 0
3 2 2 1 1 4
3 0 1 4 2 1
2 1 3 0 1 1
1 4 3 2 2 1

输出

0
0
2
6
1
2
3
1
4
3

【样例3】

见下载目录下的 ex_connected3.in 与 ex_connected3.ans

【数据规模和约定】

对于每个 1≤i≤n, 1≤ci≤n。

对于每个询问我们有: 0≤na,nb,nc≤5, 1≤a,b,c≤n 以及 a,b,c 两两不同。

对于 10% 的询问, n,Q≤10。

对于另 10% 的询问, n≤15,Q≤50。

对于另 10% 的询问, n,Q≤1000。

对于另 5% 的询问, n,Q≤50000,并且输入的树如果以点 1 为根,最大深度不超过 35(点 1 的深度为 0)。

对于另 5% 的询问, n,Q≤100000,并且输入的树如果以点 1 为根,最大深度不超过 35(点 1 的深度为 0)。

对于另 20% 的询问, n,Q≤100000,并且保证所有询问  \((na+1)^2(nb+1)^2(nc+1)^2\)  的和小于等于 1e8。

对于另 40% 的询问, n,Q≤100000,并且保证所有询问 (na+1)(nb+1)(nc+1) 的和小于等于 8e6。


这题标算大概是在虚树上dp或者分治的大讨论,是一道代码量巨大的题(myy都被坑了)

对于雪舞喵来说直接O(2^n)枚举一下联通块然后计算结果就可以拿到20分=。=

那么接下来粘代码了=。=T2的代码可能比较多,然后有一些genfac.h里的函数,都可以按字面意思理解

T1

T2

subtask1

subtask2

subtask3(错误)

subtask4

subtask6

subtask8&9

subtask10

T3

12.05.16

Yukimai

(^=。=^)

发表评论