ARFA 教堂的第二次洗礼 相关事宜&题解

傷だらけの硝子の心が、忘れかけた熱を灯す。

遍体鳞伤的琉璃之心,将快被忘却的灯火点燃。

Aimer - LAST STARDUST

白驹过隙,乌飞兔走;残雪易逝,韶华难留。岁月在命令行的闪烁间,不时地发出一声低语。
此时,在代码的字里行间和教堂给予的箴语间,我虔诚地体会着这呢喃。
「是啊,时候到了!」

好的,这里才是正题。前面那些东西是中二病晚期 Alpha1022 写的(当然这里也是他/我写的)。
第二次洗礼暂定于大年三十(2.4)延期到初一(2.5)调整到大年三十正午到傍晚 8 点,当然由于洛谷的管理员比我们还咕,所以随时会延期
这次教主 ARFA 由于一些问题,原定的唯一一道题目被亲自枪毙,将会在下一次洗礼与大家见面。
此外,这次的出题人加入了一位巨佬:坐标 TJ 的天河大佬,洛谷 ID cuking,NOI2018 Ag。

出题情况

题号 出题人
1 SXnoname
2 alpha1022
3 SXnoname
4 SXnoname
5 alpha1022 & SXnoname
6 cuking

出题人的叮嘱

  • alpha1022:

    T2 对于 SX 的同学的一个声明:LHF 不是 LiuHaiFeng 而是 LiHaoFu 大佬,谢谢,不要误会。另外请 SX 本家同学多多关注,文体两开花

  • SXnoname:

    这场比赛画风清奇,有参考北大出题风格,请各位 AKer 们慢点 AK。

  • cuking:

    无。

  • ARFA:

    我在准备下一个比赛的签到题,所以不能出水题了!

答疑

可以在此帖也可在此下评论。

题解

A

50%50\%数据?直接全排列模拟题意。
80%80 \%数据?貌似没啥用。
100%100 \%数据,考虑对每个数算贡献,一个数怎么才会贡献?当所有他的因子的数都在它后面。
那么我们只要预处理序列里它所有因子,把他们放到它的后面即可。设是它因子的数有xx个。
那么它对答案的贡献就是:aiCnx+1x!(nx1)!a_i*C^{x+1}_n*x!*(n-x-1)!
这题就O(nai)O(n \sqrt{a_i})做完了。

B

注意一个毒瘤的地方:前面的数据没有指定 mm 的大小。
然后就是显然的平衡树乱搞啦,P 操作可以统计结点的排名,Q 操作可以状压。

C

这题过于套路和裸。
首先根据裴蜀定理,可以得到:就是让我们选若干个装备使他们威力值gcd\gcd11的方案。
10%10 \%数据:直接2n2^n枚举每个装备选不选。
30%30 \%数据:设fi,jf_{i,j}表示到第ii个数,当前已选数gcd\gcdjj的方案。直接转移即可。复杂度O(n2)O(n^2)
60%60 \%数据:跟gcd\gcd有关系不妨想想反演,设g(i)g(i)表示选的所有数gcdgcdii的倍数的方案。那么有

ans=i=1nμ(i)g(i)ans=\sum_{i=1}^n \mu(i)g(i)g(i)=2nx1g(i)=2^{\lfloor\frac{n}{x}\rfloor}-1

考虑每一个它的倍数选或不选,减掉空集方案即可。
所有数据:指数可以整除分块,套路的再套上一个杜教筛就可以了,复杂度O(n23)O(n^{\frac{2}{3}})

D

这题过于裸。
基本上会pruferprufer序列都会了这道题。
题意就是求有多少棵有标号无根树,满足最大度数为MM
10%10 \%数据:直接爆搜。
30%30 \%数据:我们用pruferprufer序列求答案,用pruferprufer序列列出的式子中,(n2)!(n-2)!是已经确定了的,我们只要确定分母即可。我们考虑每一个点出现了多少次,设fi,j,kf_{i,j,k}表示当前到第ii个点,序列长度为jj,最大度数为kk,转移即可。复杂度O(n4)O(n^4)
50%50 \%数据:第三维状态限制了复杂度,这个最大为MM,直接套路的转化为至多为MM减去至多为M1M-1即可。然后DPDP就是O(n3)O(n^3)的了。
70%70 \%数据:每次转移是相同的,可以直接上快速幂优化。复杂度O(n2logn)O(n^2 \log n)
100%100 \%数据:转移过程直接NTTNTT优化即可。复杂度O(nlog2n)O(n \log^2 n)
其实直接从EGFEGF考虑更加简单。

E

其实这题本来是Alpha1022Alpha1022的,而且是维护的后缀和。
但他给我看了以后,我突然觉得这个可以维护后缀积。
20%20 \%数据:直接模拟即可。
对于ai=2a_i=2的数据:发现答案是等比数列求和,直接求路径长度即可。
对于是一条链的数据:那就是序列了,在序列上怎么做呢?发现这个是可以分治的,维护一个区间积和区间后缀积的和就行了,转移自己yyyy一下,非常简单,带修改的话,那就在线段树上维护这个分治结构。
复杂度O(qlogn)O(q \log n)
对于所有数据:基本上会了一条链,整道题就会了,树剖加上线段树去维护那个分治结构就行了,线段树上要多维护一个区间前缀积的和,这道题就做完了。复杂度O(qlog2n)O(q \log^2 n)
利用原来后缀和的ideaidea是可以在模数为素数情况下做到单次询问logn\log n的,请Alpha1022Alpha1022蒟蒻简述一下:

以上均为 SXnoname 之语,我来乱入一下。
本来后缀和的做法是这样的:维护每个结点到根结点的点权和,然后把路径从 lcalca 处截断,分别讨论。
然后是很显然的。

考虑放到后缀积上,发现这个做法只用小改,但是是 log2n\log^2 n 的。
考虑把维护的东西改成根结点到每个结点的点权前缀积之和。
然后乱搞。
修改就把子树乘上 ai+kai\frac{a_i + k}{a_i} 就好惹。

F

subtask1

直接暴力枚举删除顺序并顺便统计贡献即可,复杂度O(n!*n)

subtask2

状压DP,记下每个点删除没有,每次枚举删点转移即可,复杂度O(2^n*n)

subtask3

注意到我们并不需要知道每个点的状态,我们可以求区间的贡献,用区间DP搞定,复杂度O(n^3),自带小常数,可以过500

subtask4

区间DP的转移稍微优化一下就O(n^2)了

subtask5

直接dp好像不太好搞了,考虑利用期望线性性,先想办法求出每个点期望被贡献的次数,分别设为E[i],则答案为ΣE[i]*w[i]

E[i]貌似不太好求,先想办法求一下E[1],设f[i]表示大小为i的块的第一个点期望被贡献的次数,则E[1]=f[N]

f是可以dp的,对于f[i],每次在这个块内删除一个点,就会产生1的贡献,考虑枚举被删除的点,如果删了点j,那么块大小变为j-1,所以可以列出方程为f[i]=(Σf[j])/i+1,其中j从0到i-1,这东西稍微前缀和优化一下就是O(n)了。

再说E[i],根据期望的线性性,可以把E[i]拆成两半,分别是第i个点左半边产生的贡献和右半边产生的贡献,加起来,因为第i个点被贡献了两次,所以E[i]=f[i]+f[N-i+1]-1

这样就O(n)了

其实f[i]还有一种求法,根据期望的线性性,可以求一下块内每个点被删除时产生贡献的概率(等于期望),再求个和,而对于第j个点,它产生贡献的概率是1/j,因为只有他是前j个点里第一个被删除的情况下,他才会产生一次贡献

这样,f[i]=Σ(1/j) j从1到i。线性推逆元即可,复杂度也是O(n)

如果你用这种方法来求,那就是三次期望线性性解决了一道期望题,是不是非常优雅呢。

(至于撞题的问题,可能是我做题实在太少了,并没有发现原题(谁知道随便想的一个idea就撞了的啊),可以看到我洛谷的AC数量,这是我AC数最多的OJ了,而且也差不多顶的上其他所有OJ的一半了。。)