企业官网建设流程全解析

题目描述：给定整数数组nums（长度n ≤ 15）和整数k（1 ≤ k ≤ n-1）。将nums重新排列，要求新序列中下标第k-1个元素和下标第k个元素不能数值相同。统计符合条件的不同排列个数（相同元素产生的重复排列只算一次）。无法构造则输出0。

示例：输入2,2,3，k=1，输出2（合法排列为[3,2,2]和[2,3,2]）。

解题思路：不要暴力枚举15!种排列。用多重集合排列计数：

1. 统计每个数值出现次数cnt[x]。

2. 全部去重排列数 =n! / ∏(cnt[x]!)。

3. 两个受限位置数值相同的“有序选择数” =Σ cnt[x] * (cnt[x]-1)。

4. 两位置数值不同的比例 =[n*(n-1) - samePairs] / [n*(n-1)]。

5. 合法排列数 = 总排列数 × 该比例。

   #include <stdio.h> int main(void) { int n, k; if (scanf("%d %d", &n, &k) != 2) return 0; int cnt[101] = {0}; // 题目元素范围 1~100 for (int i = 0; i < n; i++) { int x; scanf("%d", &x); cnt[x]++; } // 总去重排列数 = n! / ∏(cnt[x]!) long long total = 1; for (int i = 2; i <= n; i++) total *= i; // n! for (int v = 1; v <= 100; v++) { for (int i = 2; i <= cnt[v]; i++) { total /= i; // 依次除以 cnt[v]! } } // 两个受限位置数值相同的有序对数 long long samePairs = 0; for (int v = 1; v <= 100; v++) { samePairs += (long long)cnt[v] * (cnt[v] - 1); } // 两位置数值不同的比例 long long denom = (long long)n * (n - 1); if (denom == 0) { printf("0\n"); return 0; } long long diffPairs = denom - samePairs; // 合法排列数 = total * diffPairs / denom long long ans = total * diffPairs / denom; printf("%lld\n", ans); return 0; }