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

brofea5 · 2025-04-12 14:21:09 · 题解

题意

求 1～2025 的排列 A_{1}～A_{2025} 使得任意的 1\le i\le j \le 2025 ，A_i\times A_j \le i\times j +2025 都成立的合法排列数量

答案取模 1\times10^9+7

思路

当 i=j 时，A_i^2 \le \lfloor i^2 +2025\rfloor，跑一次循环可知当 1013\le i\le 2025 时，A_i\le i

且由于 A_{1～1012} 都小于 1013，所以 A_{1～1013} 就会把 1～1013 都占用完，所以 A_{1014} 只能等于 1014，A_{1015} 只能等于 1015……以此类推可以得到：

对于任意的 1\le i\le 1012,1014\le j\le 2025，都满足：A_iA_j=A_ij\le ij+2025，两边同除 j 即：A_i\le \lfloor i+2025/j\rfloor，任意 j 都要满足此式，所以根据 j 的范围可以得到

我们可以看看在此式下是不是满足题目条件：(1\le i\le 1012)

由于 i+j+1\le1012+1012+1=2025 所以满足题目条件

也就是说：

• A_1$ 可以取 $1,2
• A_2$ 可以取 $1,2,3
• A_3$ 可以取 $1,2,3,4

  ……

• A_{1012}$ 可以取 $1,2,3,4......1013
• A_{1013}$ 可以取 $1,2,3,4......1013

那么 A_1 取法有 2 种，取了一个后 A_2 取法有 2 种……取了 1011 个后 A_{1012} 取法有两种，而 A_{1013} 只能取 A_{1012} 取剩下的

总共 2^{1012} 种，使用快速幂或者暴力解都行

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int qmi(int m, int k, int p) {
  long long t = m, res = 1;
  while (k ) {
    if (k&1) res = res*t%p;
    t = t*t%p;
    k >>=1;
  }
  return res;
}
int power(int m, int k, int p) {
  int res = 1;
  while (k--)
    res = res * m % p;
  return res;
}
signed main() {
  cout << qmi(2, 1012, MOD) << "\n";
  cout << power(2, 1012, MOD) << "\n";
  return 0;
}