自动搬运

查看原文

来自洛谷，原作者为

	brofea5 人生就像动态规划，在早已给定的值里反反复复地找最优解

搬运于2025-08-24 23:12:58，当前版本为作者最后更新于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;
}