2024“钉耙编程”中国大学生算法设计超级联赛（7）

Problems	AC
1001. 纠缠点对
1002. 生产机器	⊕
1003. 自动人偶	KMP 自动机，弃疗
1004. 战争游戏	○
1005. Hold’em Shark	大模拟，弃疗
1006. 怯战蜥蜴 II	多项式，弃疗
1007. 创作乐曲	⊕
1008. 循环图	⊕
1009. 关于 agKc 实在不喜欢自动化于是啥都自己合成这件事	○
1010. 故障机器人想活下去	○
1011. 蛋糕上的草莓是蛋糕的灵魂	○
1012. 华丽牧场

1002. 生产机器

某型号的作业机器人可以生产蓝色和黄色两种充能球。根据接下来 $n$ 小时的工作计划, 该机器人在第 $i$ 小时可以生产至多 $l_i$ 个黄色充能球和 $f_i$ 个蓝色充能球, 也可以不生产任何一个充能球。

在接下来 $n$ 个小时的工作结束之后, 该机器人生产的充能球将按其被生产的顺序依次装入集装箱。具体而言, 每小时内生产的充能球的顺序可以由机器人任意确定, 而前一小时生产的所有充能球都排在后一小时生产的充能球之前。

现在, 请你计算, 最终集装箱中装入的充能球所构成的序列共有多少种可能。两个序列不同当且仅当其包含的充能球总数不同, 或者存在一个 $i$, 使得两个序列中生产的第 $i$ 个充能球颜色不同。由于答案可能很大, 你只需要输出答案对 $10^9+7$ 取模的结果。

思维 + 组合数学

如何避免重复？在组合数学中一个常见的思想：钦定！

假如我们现在想要一个序列。我们这样操作：从前往后，每个时段需要尽可能多出球，直到需要的颜色这个时段没有为止，再换下一个时段 or 在这个时段结束。

这样的话能保证序列是不重的。

于是我们基于此设计 dp(i, j) 表示到第 i 个时段，这一个时段生产的第一个小球颜色为 j，对应的合法方案数。

我们需要枚举下一个时段的 dp(i + 1, k) 进行更新。根据前面的设计，k 这个颜色需要在 i 时段全部用完；另一种颜色则随意。

假如第 i 个时段，填上第一个球以后，两种球分别还剩 x 和 y 个。假如这个时段这 x 个球是要全部被用完的话，方案数我们有：

$$
\sum_{i=0}^y\binom{i+x}{x}=\binom{x+y+1}{x+1}
$$

这个式子是怎么从左边到右边的？x + y + 1 个物品，选其中的 x + 1 个，相当于，钦定在 x + i + 1 个位置选到了 x + 1 个，然后在前 x + i 个里面选 x 个

假如在当前时段结束选球，那么就是：

$$
\sum_{i=0}^x \sum_{j=0}^y\binom{i+j}{i}
=\sum_{i=0}^x \binom{i+y+1}{i+1}
=\sum_{i=1}^{x+1} \binom{i+y}{i}
=\binom{x+y+2}{x+1} - 1
$$

复杂度 $O(n + w)$

1007. 创作乐曲

通过发现性质，减少决策点！

1008. 循环图

坎格鲁斯普雷被困在了一张循环图里，这张循环图有无数个节点，初始时坎格鲁斯普雷在 1 号节点。

循环图是边存在着一定循环关系的图，循环图里面的边可以用循环周期 $n$ 和 $m$ 对三元组 $\left(u_i, v_i, w_i\right)\left(1 \leq u_i \leq n, u_i+1 \leq v_i \leq 2 \times n, 1 \leq w_i \leq 10^9\right)$ 表示。每对三元组 $\left(u_i, v_i, w_i\right)$ 表示，对于循环图内所有的满足 $s=u_i+k \times n, t=v_i+k \times n(k \in N)$ 的点对 $(s, t)$ ，都存在有 $w_i$ 条从点 $s$ 通往点 $t$ 的边。

现在，坎格鲁斯普雷知道了这张循环图的第 $L$ 个节点到第 $R$ 个节点各存在着一个出口，坎格鲁斯普雷需要到达这些节点中的任意一个才能逃出循环图（到达有出口存在的节点后不一定要立刻逃出）。坎格鲁斯普雷想请你帮他算算，他有多少种逃出这张循环图的方式。由于答案可能很大，你需要输出答案对 $10^9+7$ 取模后的结果。

设 calc(i) 为走到 [1, i] 节点的方案数只和，ans = calc(R) - calc(L - 1)

设 f(i) 为走到 i 节点的方案数之和，这个东西是很好 dp 的。那我们直接先求出 f(1), f(2) … f(n)

然后搞出我们的转移矩阵。这里有一个技巧是，我们直接搞出一个大转移矩阵，这个转移矩阵相当于步长是 n，这样我们 pow 的指数就变成了 x / n，最后边角 O(x % n) 扫一下即可。

1011. 蛋糕上的草莓是蛋糕的灵魂