P12131 客流量上限 题解

· · 题解

题目简述

应该都能理解，就不多说了。

题目分析

针对一句话：

对于任意分店 i 和 j(1\le i,j\le2025)，它们的客流量上限 A_i 和 A_j 的乘积不得超过 ij+2025。

所以，对于任意分店 i(1\le i\le2025)，它的客流量上限 (A_i)^2 不得超过 i^2+2025。

(A_i)^2\le i^2+2025 A_i\le\sqrt{i^2+2025}

很容易想到打表：

for (int i = 1; i <= 2025; i++) cout << i << ':' << (int)sqrt(i * i + 2025) << '\n';

打表发现：

A_i\le i(i\ge1013)

因为 A_{1\sim1012}\le1012，已经把 1\sim1012 占满了，所以 A_{1013\sim2025} 只有唯一解，即 A_i=i(1013\le i\le2025)。

那么当 1\le i<1013\le j\le2025 时，

A_iA_j=A_ij A_iA_j\le ij+2025

则，

A_ij\le ij+2025 A_i\le i+\frac{2025}{j} A_i\le\lfloor i+\frac{2025}{j}\rfloor A_i\le i+\lfloor\frac{2025}{j}\rfloor

由于 1013\le j\le2025，所以，

A_i\le i+1 A_i\in[1,i+1]

根据此式，得出：

$A_2$ 选的不与 $A_1$ 选的重复，有 $2+1-1=2$ 种选择； $A_3$ 选的不与 $A_{1\sim2}$ 选的重复，有 $3+1-2=2$ 种选择； …… $A_i$ 选的不与 $A_{1\sim i-1}$ 选的重复，有 $i+1-(i-1)=2$ 种选择。 所以答案就是 $2^{1012}\mod(10^9+7)$。 ## 重点代码 `pw` 函数递归调用求 $2$ 的幂。 个人认为，位运算比乘除法更省时间，能省一点是一点（普通的方法，` << 1` 可以改成 ` * 2`）。 ```cpp int pw(int x){ if (!x) return 1; return (pw(x - 1) << 1) % MOD; } ```