A 四章

题意：有个和个，把它们分成尽量少的组，使得每组的和不超过。

我们使用一个贪心算法，每次先选择尽可能多的，再选择尽可能多的分成一组。可以证明这样能够得到最优解。因为如果在还没被选的数中，把一个换成两个，答案一定不会变劣；所以如果在新选出的一组里存在两个、且存在至少一个没被选，把两个换成一个必然更优。

由于数据范围为，无法直接模拟。

可以先计算出若和都足够多，每组要选几个、几个。然后再不断使用这种方案直到或之一不够。之后下一组必定会将或选完。之后就只剩一种数了，直接计算即可。

复杂度。

B 一章

以下图片中红点为割点、红边为桥。

当时：

• 若，构造一个三元环即可。
• 若，构造两个点之间连一条边即可。
• 若，无解。因为可以发现若一个桥边的某个端点不是割点，那这个端点必定是度点。

当时：

• 按照以下方法构造：

当时：

• 按照以下方法构造：

C 欢乐斗地主

设第张牌被替换的时间为，那么地主的操作就等于随机生成了一个排列，而这个排列的答案就是从左到右第一个且的位置。

如果我们对于每个，求出有多少个排列满足答案，即可求出原问题的答案。设以上的答案为，那么就等于满足以下条件的排列个数：对于所有的且的位置，满足。

对于一个，我们可以用以下方法求：从左到右枚举满足且的，设之前已经有个了，那么的选择方案需要满足且和前个的选择不同，即答案要乘上。最后，设总共枚举了个数，那么剩下个数的决策还没确定，需要再乘上。

容易发现根据以上方法，可以方便地从小到大一次性求出所有。这样我们就在的时间解决了此题。

D 买糖果

一句话题意：求的所有非空子集的和的积。

可以采用meet in middle。先把前一半是空集和后一半是空集的情况用的复杂度处理掉，然后就是前一半和后一半都非空的情况。

设前一半的所有情况的和为，后一半所有情况的和为，那么要求的就是。

设， 答案就是。那么我们对所有跑个多点求值即可解决这个问题。

复杂度为。

E 正整数序列

以下定义。

定义为满足以下条件的长为的数组的个数：

• 。
• 对于任意，是的子序列。
• 对于最后一个非空序列，满足中不存在数字。特殊地，若，表示没有任何限制。

那么答案就是。

对于转移，一共有两种情况：

• 为空，那么。
• 中第一个数字为，那么为了防止被计算重，中到间不存在；但是若中到间为空，中到间不存在。则依此类推，可得。

这样便可以解决这个问题。复杂度。

F 时之魔法

我们枚举所有原串或反串中两个后缀，计算它们的贡献，一共有以下几种情况：

• 和属于两个不同的串。那么贡献为乘上和所在的串 翻转/没翻转 的概率之积。
• 和属于同一个串，且同为 原串/反串。贡献计算方式与上种情况类似，但概率只需乘一次。
• 和属于同一个串，且一个为原串、另一个为反串。贡献为。

对于计算贡献的方式，我们先假定每一对后缀都属于第一种情况。那么总贡献即为每一对后缀的概率之积乘上它们在后缀树上的深度。我们可以利用广义后缀自动机建立后缀树，然后在上面求出答案。

之后我们需要减去属于同一个串的所有后缀的贡献，并重新计算它们的贡献。那么我们可以仅对同一个串的原串与反串建立后缀树，重新计算贡献。而这个过程也可以通过在后缀树上解决。

设字符串总长为、字符集大小为，我们在的复杂的内解决了此题。