Permutation (USACO Gold 2021 US Open)

此题步骤和细节较多，难度较大。

新增的节点或者在原有节点的外接三角形内（题目友好，规定不会和线或者点重合），或者在外接三角形的三个角的对顶角内。就是下图A,B,C,D区间

    \ B /
     \ /
      x
     / \
    / A \
 --<----->--
 C/       \D
 /         \

所以新增一个节点的时候，是否是合法的，是可以 $\mathcal{O}(1)$ 判断的（具体就是用叉乘来做判断，见程序）。

下面看怎样求解整个序列。排列相关的题，往往会向bitmask DP的方向去想，此题确实比较像bitmask DP，可以列出状态和转移方程，但最大的障碍是 $n=40$ ，而且没有找到meet-in-the-middle方法。所以bitmask DP是不通的，需要继续找降低复杂度的办法。

用最简单的穷举的方式，可以对每个排列检查是否是合法的，这样可以过 $6$ 个测试点。

正解是用可以用 $4$ 维DP来做，状态定义为： $\text{dp}[i][j][k][l]$ , $i,j,k$ 是上面提到的外接三角形三个顶点, $l$ 是已经放了多少个点。从 $l-1$ 到 $l$ 新增一个节点的时候，可以看到仅有有两种情况：

新增节点在原有外接三角形里面，这样的话， $i,j,k$ 不变，新的方案数是 $l-1$ 个节点时候方案数的 $M_{ijk}-(l-1)$ 倍， $M_{ijk}$ 是所有节点中，在三角形 $ijk$ 内的总数（包含 $i,j,k$ ），可以看到三角形内每个点都符合要求， $M_{ijk}-(l-1)$ 就是最后新增的节点的可选方案数。
新增节点在原有外接三角形的外面，则 $i,j,k$ 中有一个是新增出来的，我们枚举 $i,j,k$ 三角形中所有点 $x$ ， $x$ 就是原有另外一个三角形顶点，对于每个 $x$ ，都有三种情况（ $x$ 和 $ijk$ 中的两个组合，作为原有三角形），把方案数加起来就可以了。

为了让 $i,j,k$ 之间的顺序好处理，也为了减少计算量，我们可以将外接三角形的节点顺序固定（比如编号从小到大），然后 $\text{dp}[i][j][k][3]=6$ 就可以统计这个三角形顶点间的6种顺序。

状态转移如下：

\text{dp}[i][j][k][l] = \text{dp}[i][j][k][l-1] \cdot (M_{ijk}-l+1) + \sum_{x \in \triangle ijk} (dp[i,j,x][l-1] + dp[i,k,x][l-1] + dp[j,k,x][l-1])

其中， $M_{ijk}$ 是 $i,j,k$ 三角形内总点数（包含 $i,j,k$ ）, $x$ 是 $i,j,k$ 三角形内任一点（不包含 $i,j,k$ ）。 $\text{dp}[i,j,x][...]$ 的意思是把 $i,j,x$ 排序后作为三个下标。

四维DP，再加每次更新状态需要 $\mathcal{O}(n)$ ，所以复杂度是 $\mathcal{O}(n^5)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;          // <= 40
pi ps[45];      // x,y <= 1e4
int dp[45][45][45][45];
int ans;
const int M = 1e9+7;
 
int cross(pi a, pi b) {
    return a.first * b.second - a.second * b.first;
}
 
pi sub(pi a, pi b) {
    return {a.first-b.first, a.second-b.second};
}
 
bool sameSide(pi p1, pi p2, pi a, pi b) {
    int c1 = cross(sub(b,a), sub(p1,a));
    int c2 = cross(sub(b,a), sub(p2,a));
    if ((ll)c1 * c2 >= 0) return true;
    else return false;
}
 
bool inside(pi p, pi a, pi b, pi c) {
    if (sameSide(p,a,b,c) && sameSide(p,b,a,c) && sameSide(p,c,a,b))
        return true;
    else return false;
}
 
void sort3(int &a, int &b, int &c) {
    int x[3] = {a,b,c};
    sort(x, x+3);
    a = x[0], b = x[1], c = x[2];
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &ps[i].first, &ps[i].second);
 
    vector<int> pe(n);
    for (int i = 0; i < n; i++)
        pe[i] = i;
    
    for (int l = 3; l <= n; l++) {
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    if (l == 3) {
                        dp[i][j][k][l] = 6;
                    } else {
                        int cnt = 3;
                        for (int x = 0; x < n; x++) {
                            if (x == i || x == j || x == k) continue;
                            if (inside(ps[x], ps[i], ps[j], ps[k])) {
                                cnt++;
                                int a = i, b = j, c = x; sort3(a,b,c);
                                // case 2: surrounding triangle became larger going from l-1 to l
                                dp[i][j][k][l] = (dp[i][j][k][l] + dp[a][b][c][l-1]) % M;
                                a = i, b = k, c = x; sort3(a,b,c);
                                dp[i][j][k][l] = (dp[i][j][k][l] + dp[a][b][c][l-1]) % M;
                                a = j, b = k, c = x; sort3(a,b,c);
                                dp[i][j][k][l] = (dp[i][j][k][l] + dp[a][b][c][l-1]) % M;
                            }
                        }
                        if (cnt > l-1)  // case 1: triangle stayed same, added an internal vertex
                            dp[i][j][k][l] = (dp[i][j][k][l] + (ll)dp[i][j][k][l-1] * (cnt - l + 1)) % M;
                        if (cnt == n && l == n)
                            ans = (ans + dp[i][j][k][l]) % M;
                    }
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}