2021-11-10 KT1

这一部分的总结先鸽一会。

# 莓良心 *

莓在执行任务时，收集到了 $n$ 份岩浆能源，其中第 $i$ 份的能量值是 $w_i$ ，她
决定将它们分成恰好 $k$ 组带回基地，每一组都要有至少 $1$ 份能源。
每一组能源会对运输设备产生负荷值，若该组有 $x$ 份能源，这 $x$ 能源能量值之和为 $y$, 则产生的负荷值为 $x\times y$ 。
每种分组方案产生的负荷是每一组能源产生的负荷值总和，莓想知道所有可能的分组方案产生的负荷之和对 $998244353$ 取模的结果 。

$$1\le n\le 1e6$$

由于涉及一点二项式反演内容故这里不全。

md 补考试总结去了先不写了。

# 团不过 *

由比滨结衣和雪之下雪乃在玩 $Nim$ 游戏。
共有 $n$ 堆石子，双方轮流操作，每次可以从一堆非空石子堆中取走任意个石子，取走最后一个石子的人胜利。
她们决定让由比滨结衣先手，但忘记了每堆初始时含有石子的数目，只知道
每堆至少有 $1$ 个石子，但数目小于 $2^n$ ，且每堆石子的数目互不相同。
一共有多少种可能的情况使得由比滨结衣能够取胜呢？
两种情况不同当且仅当存在一堆石子在两种情况中含有的石子数目不同。
由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果。
友情提示：在 $Nim$ 游戏中，先手必胜等价于各堆石子数目异或之和不为 $0$ 。

$$n\le 1e7$$

我看的时候完全没有思路

然后，这个每堆石子数量互不相同是个极其有用的结论。

先做一步补集转换，先手必胜的方案数等价于总方案数减去先手 LOST 的方案数

记一个 $g_i$ 表示到第 $i$ 堆的石子状况的总方案数，递推式容易得到：

$$g_i = \prod\limits_{i=1}^i (2^n - i)$$

记一个 $f_i$ 表示到第 $i$ 堆先手必败石子状态的方案数，做一下讨论：

• 若前 $i-1$ 堆是先手必败，则说明其前缀异或和为 $0$ ，那这一堆也要是 $0$ ，而我们发现每堆石头得大于 $1$ 所以这不合法，于是我们要减去 f_

• 若前 $i-2$ 堆是先手必败，则此时的前缀异或和为第 $i - 1$ 堆的堆数，那这一堆也得是，不难发现不合法，也得减去。

所以可以得到递推式：

$$f_i=g_i - f_{i-1} - f_{i-2}\times \binom{i-1}{1} \times (2^n - 1 - (i - 2) )$$

# 尽梨了 *

丰之崎学园附近共有 $n$ 个商店，在时刻 $0$ 时，英梨梨从学园出发开始购物。
从学园走到任意一个商店，或从一个商店走到另一个商店需要 $1$ 单位时间。
如果英梨梨在时刻 $t$ 到达了商店 $i$，她需要先花费 $a_i\times t + b_i$ 的时间排队
然后才能购买这家商店的物品。
英梨梨想知道，在时刻 $T+ 0.5$ 之前她最多能在多少个不同商店买到物品呢？
这里假定只会在走路和排队上消耗时间，购买物品不消耗时间。

$$n\le 2e5,T\le 1e9$$

这是一道感觉比较套路的题，首先直觉上感觉到若我们确定了一些选东西，那拿出来的顺序是一定的，于是我们想到先按一个东西排序。

那么我们考虑在 $t$ 时刻选到 $i$ 然后立刻选 $j$ 的消耗是什么，这样通过交换邻项解一个不等式可得出排序的关键字。

然后就可以 $dp$ 了，设 $dp_{i,j}$ 表示到第 $i$ 个店上一个走到 $j$ 的最小时间，转移显然。

然后我们考虑这个只要 $a_i > 0$ 时间增长速率极快，于是我们把 $a_i=0$ 的拿出了先不管，跑一遍 $dp$ ，大概 $\log$ 层就会跑满时间上界，再对 $a_i=0$ 的做一遍贪心。

# 七负我 *

有一个 $n$ 个点 $m$ 条边的图。给一些点分配一些点权（可以是任意非负实数）使得所有点点权和为 $x$（点权可以为 $0$）。一条边 $\langle u,v \rangle$ 的贡献为 $u$ 的点权与 $v$ 的点权的乘积。问所有边贡献和最大是多少。

$$1\le n\le 40,1\le x\le 100$$

nb 贪心题！

直觉上可以推出的结论是一定是把点权和平均分配到点上，然后贡献尽量多的边是更优秀的。

然后你可能会想到放在一张完全图上我是不敢想到

考虑证明这个 nb 结论。

对于点对 $(u,v)$ 设他们无边，设当前最优的答案给 $u$ 分配了 $f_u$ 权值，给 $v$ 分配 $f_v$ ，连接他们的点权和不妨记做 $s_u, s_v$ ，那这一部分对于答案的贡献就是 $f_u\times s_u + f_v\times s_v$

不妨设 $s_u\ge s_v$ 可以发现，把分配给 $v$ 的权全给 $u$ 一点不劣。

然后就是一个最大团的问题了， $\texttt{meet in mid}$ 一下即可解决。

感觉这种看着就很贪心结论的题还是要凭着直觉大胆猜测结论，再小心求证。

而贪心结论的证明则考虑交换邻项来反证或者从一些局部情况来归纳

这里就是要观察一对无边的点对对答案的贡献来归纳了。

感觉比较玄妙。