感觉这个题的状态定义挺有 LIS 的套路的。感觉这个题可以用最长上升子序列的那种方法去定义状态去做，但是我用了另一种转化方式。

相对于普通的 LIS 计数，我们不仅需要考虑 LIS 的长度，还需要让护卫的编号（以下定义为“关键数字”）在原序列中单调递增地出现。如何根据这两个限制来定义状态呢？

有一种求 LIS 的方式：定义一个集合 $S$，初始时 $S=\varnothing$，对于每一个 $a_i$，如果 $S$ 中存在最小的 $x$ 使得 $x>a_i$，那么删去 $x$ 加入 $a_i$，否则直接加入 $a_i$，最终 $|S|$ 即为 LIS。

我们可以根据这种方式设计 dp 状态。定义 $dp_{S,T}$ 表示当前已经考虑了 $S$ 中的数，在集合中的数有 $T$，的方案数。这样定义状态数时我们可以用 $|T|$ 限制 LIS 的长度。在转移的时候，我们统计一下 $S$ 中出现了几个关键数字，在加入新的数字的时候判断一下是否是关键数字，如果是的话只能加入第一个没出现的，这样就能考虑到关键数字顺序的限制。

下面分析时间复杂度。由于 $T\subseteq S$，所以枚举状态时间复杂度是 $O(3^n)$ 的，转移的时候枚举新加入的数时间复杂度是 $O(n)$ 的，所以总时间复杂度为 $O(n3^n)$。在实现的时候用unordered_map存储子集状态就可以了，在实现时需稍微注意一下常数。

代码实现可以参考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int a[20], sp[20];
unordered_map<int, ll> dp[50010];
void solve() {
    int n = read(), k = read();
    if (k == 1) {cout << 1; return;}
    for (int i = 1; i <= k; i++) a[i] = read();
    for (int i = 1; i <= k; i++) sp[a[i]] = i;
    dp[0][0] = 1;
    for (int b = 0; b < (1 << n); b++) {
        int fst = k + 1;
        for (int i = 1; i <= k; i++)
            if (!((b >> (a[i] - 1)) & 1)) fst = min(fst, i);
        for (auto &it : dp[b]) {
            int sb = it.first; ll val = it.second;
            for (int i = 1; i <= n; i++) {
                if ((b >> (i - 1)) & 1) continue;
                if (sp[i] && i != a[fst]) continue;
                int bit = 1 << (i - 1);
                int nb = b | bit, nsb = sb | bit;
                int tr = sb & (~((1 << i) - 1));
                if (tr) {
                    int j = __builtin_ctz(tr) + 1;
                    int dl = (1 << n) - 1 - (1 << (j - 1));
                    nsb &= dl;
                }
                dp[nb][nsb] += val;
            }
        }
    }
    ll ans = 0;
    for (auto &it : dp[(1 << n) - 1])
        if (__builtin_popcount(it.first) == k) ans += it.second;
    cout << ans;
}