2017-Sp148-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,700px)]]
== 流水账 ==
开场各自读题，大概开了B、C、F，然后榜过了F，思考再三决定强上搜索，cjb犯了愚蠢错误'''F3y59'''。yzc和sub推出了C，yzc上机'''C1y76'''。sub想好了D，上机wa了，观察得到规律，'''D2y99'''。三个人一起讨论I，得到了简化模型，查数列表得到公式，但是取模很难处理，进行了暴力尝试，wa了一发。之后发现规律有误，反复研究，得到正确规律，'''I2y171'''。cjb上机敲B的树链剖分，sub想好了H，yzc和cjb觉得B的做法太复杂，决定先上H，cjb敲NTT，sub补上wa了，测大数据发现溢出，'''H2y247'''。cjb和yzc想好了简洁做法，yzc上机wa了2发，cjb写暴力，sub和yzc查错，发现有边界漏洞，之后'''B3y266'''。
== 总结 ==
=== chenjb ===
感冒咳嗽好难受，开场签到sb了2发mdzz。今天得益于开题顺序，不断拖后，经过深思熟虑后的B变得美轮美奂，节省了大量coding的时间和效率。毛子的数学真的好....另外毛子延续了封榜之后丧心病狂的一贯做派。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：首先我们考虑，单个的 0和单个的 1是否出现在编码规则里。显然只有可能存在某个才有意义（否则是答案是 N 或者 −1)。不妨设存在 0 且不存在 1。因为是prefix-free编码系统，有一个很显然的性质是：串 w是否能被解码，等价于 0^k^w能否被解码(之前放 k个 0)。对于串 S 假设我们固定了一段不能解码的后缀，考虑前面一段应该怎么划分。首先，由于0能被解码，之前划分的每一段至少包含一个 1，即最大划分数是 1的个数。此外，我们也能构造出这个方案：对于每一个1 把它和之前连续的 0 并在一起，独立成一段。所以现在问题就是，找到最短的一段不能解码的后缀，然后答案再加上之前 1的个数。为了快速找合法后缀，我们可以对编码倒着建AC自动机，并拿 S 在图里跑一跑。一旦到了一个不是任何编码结束点的点即可停止。

 * B：考虑虚树构建方式，显然按dfn序依次添加并算相邻节点贡献，修改操作则只会对至多2个dfn序相邻点产生影响，简单维护即可。

 * C：所有-1位置的度数的期望显然是相同的，对于一个点v，每条边(u,v)的贡献为v*(n-u的子树大小)，于是v的贡献为E(度数)*n*v-v*(n-1)。

 * D：答案是4a-1/3。

 * E：sub

 * F：从大到小依次搜索，用map记状态进行记忆化，加可行性剪枝即可。

 * G：用原根表示每个值，变成区间加区间gcd，拆分后维护区间gcd和前缀和，每次拆分区间和头元素求gcd即可。

 * H：考虑不断求相邻差的过程，先把A数组乘以(x-1)^n^，把n之后的项丢掉，再除回来即可，使用FFT。

 * I：由数列表得到通项公式，p以内用通项公式计算，有f[k*p]=f[k]，递归计算即可。

 * J：cjb

流水账

开场各自读题，大概开了B、C、F，然后榜过了F，思考再三决定强上搜索，cjb犯了愚蠢错误F3y59。yzc和sub推出了C，yzc上机C1y76。sub想好了D，上机wa了，观察得到规律，D2y99。三个人一起讨论I，得到了简化模型，查数列表得到公式，但是取模很难处理，进行了暴力尝试，wa了一发。之后发现规律有误，反复研究，得到正确规律，I2y171。cjb上机敲B的树链剖分，sub想好了H，yzc和cjb觉得B的做法太复杂，决定先上H，cjb敲NTT，sub补上wa了，测大数据发现溢出，H2y247。cjb和yzc想好了简洁做法，yzc上机wa了2发，cjb写暴力，sub和yzc查错，发现有边界漏洞，之后B3y266。

总结

chenjb

感冒咳嗽好难受，开场签到sb了2发mdzz。今天得益于开题顺序，不断拖后，经过深思熟虑后的B变得美轮美奂，节省了大量coding的时间和效率。毛子的数学真的好....另外毛子延续了封榜之后丧心病狂的一贯做派。

oipotato

subconscious

题解

• A：首先我们考虑，单个的 0和单个的 1是否出现在编码规则里。显然只有可能存在某个才有意义（否则是答案是 N 或者 −1)。不妨设存在 0 且不存在 1。因为是prefix-free编码系统，有一个很显然的性质是：串 w是否能被解码，等价于 0^kw能否被解码(之前放 k个 0)。对于串 S 假设我们固定了一段不能解码的后缀，考虑前面一段应该怎么划分。首先，由于0能被解码，之前划分的每一段至少包含一个 1，即最大划分数是 1的个数。此外，我们也能构造出这个方案：对于每一个1 把它和之前连续的 0 并在一起，独立成一段。所以现在问题就是，找到最短的一段不能解码的后缀，然后答案再加上之前 1的个数。为了快速找合法后缀，我们可以对编码倒着建AC自动机，并拿 S 在图里跑一跑。一旦到了一个不是任何编码结束点的点即可停止。
• B：考虑虚树构建方式，显然按dfn序依次添加并算相邻节点贡献，修改操作则只会对至多2个dfn序相邻点产生影响，简单维护即可。
• C：所有-1位置的度数的期望显然是相同的，对于一个点v，每条边(u,v)的贡献为v*(n-u的子树大小)，于是v的贡献为E(度数)*n*v-v*(n-1)。
• D：答案是4a-1/3。
• E：sub
• F：从大到小依次搜索，用map记状态进行记忆化，加可行性剪枝即可。
• G：用原根表示每个值，变成区间加区间gcd，拆分后维护区间gcd和前缀和，每次拆分区间和头元素求gcd即可。
• H：考虑不断求相邻差的过程，先把A数组乘以(x-1)ⁿ，把n之后的项丢掉，再除回来即可，使用FFT。
• I：由数列表得到通项公式，p以内用通项公式计算，有f[k*p]=f[k]，递归计算即可。
• J：cjb

附加文件

• 1.png by chenjb