题目
题意
- 给一个数字n，构造出一个全排列的数组a，满足上面二分结果为true
- 请求出不同全排列数组a的数量，答案模1e9+7
思路
- 模拟：按照二叉查找树的思路，模拟这个二分所有可能遇到的mid，使得判断条件成立（为什么落在最后的点上？因为是折半查找，搜索树上没有重复的节点）
- 这样得到了必须大于等于x位置的数量，和必须小于x位置的数量，也就是知道了剩下没有遇到的位置该如何排列（全排列）
ans = C[Cles][les.size()] * fact[les.size()] % mod;计算小于的数量（特殊处理遇到pos节点的位置，即忽略）ans = (ans * (C[Cgre][gre.size()] * fact[gre.size()] % mod)) % mod;计算大于的数量ans = (ans * fact[n - les.size() - gre.size() - 1]) % mod;计算剩余的排列数量- 需要用到组合数和计数原理，和二分
代码
ini
复制代码
const double PI = acos(-1.0); const int N = 1010, mod = 1e9 + 7; int C[N][N]; int fact[N]; void solve() { int n, x, pos; cin >> n >> x >> pos; vector<int> gre, les; vector<int> idx; int l = 0, r = n; while(l < r) { int mid = l + r >> 1; idx.push_back(mid); if(mid <= pos) { l = mid + 1; if(mid != pos)les.push_back(mid); } else { r = mid; gre.push_back(mid); } // debug1(mid); } int Cles = x - 1; int Cgre = n - x; // debug2(Cles, Cgre); // debug2(les.size(), gre.size()); int ans = C[Cles][les.size()] * fact[les.size()] % mod; ans = (ans * (C[Cgre][gre.size()] * fact[gre.size()] % mod)) % mod; ans = (ans * fact[n - les.size() - gre.size() - 1]) % mod; cout << ans << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); C[0][0] = fact[0] = 1; for (int i = 1; i <= 1000;i ++) { C[i][0] = C[i][i] = 1; fact[i] = (fact[i - 1] * i) % mod; for (int j = 1; j < i;j ++) { C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } } // caseT solve(); return 0; }
