题意
给定 \(n\) 和 \(1,\cdots,n\) 的一个大小为 \(k\) 的子序列 \(a\)。求有多少长度为 \(n\) 的排列 \(p\)，使得 \(a\) 是 \(p\) 的一个 LIS。\(k\leq n\leq 15\)。
题解
题意看上去一脸 DP 套 DP 的样子，经典地，我们这样刻画 LIS：维护一个集合 \(S\)，每次考虑一个数 \(x\)，将 \(S\) 中第一个大于 \(x\) 的数替换成 \(x\)，若不存在，则直接加入 \(x\)，最终 \(S\) 的大小就是 LIS 的长度。把题述条件拆成两个部分：一部分是 \(a\) 在 \(p\) 中是按值从小到大依次出现的，另一部分是 LIS 长度为 \(k\)。设计 DP：令 \(f_{S,T}\) 表示考虑了 \(S\) 中的数，计算 LIS 时维护的集合为 \(T\) 时的方案数。转移时枚举加入一个数 \(x\notin S\)，\(T\) 直接按照上述方式更新。注意若 \(x\in a\)，则需要保证 \(a\) 中 \(<x\) 的数已经加入 \(S\) 中。最终答案即为 \(\sum\limits_{|T|=k}f_{U,T}\)。注意到 \(T\subseteq S\)，因此状态数为 \(\mathcal{O}(3^n)\)，时间复杂度为 \(\mathcal{O}(n3^n)\)。
我偷懒写 unordered_map 也过了。
代码
#include <bits/stdc++.h>using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
const int N = 15, S = 1 << 15;template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> inline void chk_min(T &x, T y) { if (y < x) x = y; }
template<typename T> inline void chk_max(T &x, T y) { if (x < y) x = y; }int n, k, mask[N], pc[S];
ll ans;
unordered_map<int, ll> f[S];
bool mark[N];int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> k;for (int i = 1, s = 0, x; i <= k; ++i) {cin >> x, --x;mark[x] = 1;mask[x] = s, s ^= 1 << x;}for (int s = 1; s < 1 << n; ++s) pc[s] = pc[s ^ lowbit(s)] + 1;f[0][0] = 1;for (int s = 0; s < (1 << n) - 1; ++s) {for (auto [t, val] : f[s]) {for (int x = 0; x < n; ++x) if (~s >> x & 1) {if (mark[x] && (s & mask[x]) != mask[x]) continue;int ns = s ^ (1 << x), nt = (t ^ lowbit(t & -(1 << x))) ^ (1 << x);if (pc[nt] <= k) f[ns][nt] += f[s][t];}}}for (int t = 0; t < 1 << n; ++t) if (pc[t] == k) ans += f[(1 << n) - 1][t];cout << ans;return 0;
}