1 条题解
-
0
【本题解由站长编写】
用状态 (已使用数字的集合 mask,最后一个数字 last) 记忆化统计合法补全数。构造第 K 个排列时,按候选数字从小到大遍历:若该候选的补全数小于 K,跳过并从 K 中减去这部分,否则选它并进入下一位。状态数 O(N·2^N),总计算 O(N²·2^N),不必枚举前面的几十万个完整排列。题目保证 K 对应的合法排列存在。
代码(C++17)
#include <bits/stdc++.h> using namespace std; int n, mat[12][12]; long long k, memo[1 << 10][11]; long long countWays(int mask, int last) { if (mask == (1 << n) - 1) return 1; long long &answer = memo[mask][last]; if (answer != -1) return answer; answer = 0; for (int v = 0; v < n; ++v) if (!(mask >> v & 1) && (last == n || mat[last][v])) answer += countWays(mask | (1 << v), v); return answer; } int main() { cin >> n >> k; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> mat[i][j]; memset(memo, -1, sizeof(memo)); int mask = 0, last = n; for (int pos = 0; pos < n; ++pos) { for (int v = 0; v < n; ++v) { if (mask >> v & 1 || (last != n && !mat[last][v])) continue; long long count = countWays(mask | (1 << v), v); if (k > count) { k -= count; continue; } cout << v << (pos + 1 == n ? '\n' : ' '); mask |= 1 << v; last = v; break; } } return 0; }
- 1
信息
- ID
- 4273
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者