题解：P12131 [蓝桥杯 2025 省 B] 客流量上限

· · 题解

首先可以根据 i=j 时的限制计算出一个上界 a_i \le \sqrt{i^2+2025}，但是这个条件并不是充分的。不过它引出了一个重要观察：当 i \ge 1013 时一定有 a_i \le i。

注意到 1 位置只可以填 1,2，考虑每个位置和 2025 的限制，有 2025a_i \le 2025i+2025，即 a_i \le i + 1。

接下来我们证明 a_i \le \min(\sqrt{i^2+2025},i+1) 就是充要条件，必要性已经在前面完成证明。此时会有

a_i \le \begin{cases} i+1 & i < 1013\\ i & i \ge 1013\end{cases}

将 i,j(i \le j) 分为三类：

因此上述条件是充要的。

计数部分考虑从 1 \to 2025 一个一个填，1 \sim 1012 每个位置都只有两个选法，1013 \sim 2025 每个位置只有唯一填法。因此答案是 2^{1012} \equiv 781448427 \pmod {10^9+7}。