受限序列重排

题目描述给定整数数组nums长度n ≤ 15和整数k1 ≤ k ≤ n-1。将nums重新排列要求新序列中下标第k-1个元素和下标第k个元素不能数值相同。统计符合条件的不同排列个数相同元素产生的重复排列只算一次。无法构造则输出0。示例输入2,2,3k1输出2合法排列为[3,2,2]和[2,3,2]。解题思路不要暴力枚举15!种排列。用多重集合排列计数统计每个数值出现次数cnt[x]。全部去重排列数 n! / ∏(cnt[x]!)。两个受限位置数值相同的“有序选择数” Σ cnt[x] * (cnt[x]-1)。两位置数值不同的比例 [n*(n-1) - samePairs] / [n*(n-1)]。合法排列数 总排列数 × 该比例。#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; }