P7529 [USACO21OPEN] Permutation G 题解

· · 题解

G组练习总结#10

好喜欢妙妙题！

stO Benq Orz

题目大意

Bessie 喜欢画画，现在它给你了 n(n\leq40) 个点，她将按照一定的顺序去连接这些点，0\le x_i,y_i\le 10^4。

Bessie 会先选择一个这 n 个点的排列，记为 p_1,p_2\dots p_n，然后按照以下的方式去操作：

首先，她会将 p_1,p_2,p_3 连成一个三角形。

然后对于 i(4\leq i\leq n)，我们找到所有可以从 p_i 看到的 p_j(j<i)，即连接 p_i,p_j 的线段不与任何先前存在的线段相交（端点除外），连接 (p_i,p_j)。

Bessie 会一直这样操作下去，她限制我们，对于所有 i(4\leq i\leq n)，新连接的线段数必须刚好是 3。

现在她请我们求出所有合法的排列 p 的个数，答案数对 10^9+7 取模。

题目保证没有任何三个点共线。

解题思路

第一个操作会给我们的图一个初始的大三角形，这没什么好说的。

我们可以试着分析加入 p_4 时需要满足些什么条件？先看图：

目前状况是这样的：

我们分别讨论 p_4 的位置，如果 p_4 在三角形里面，那很好处理，条件直接满足了！跟三角形三个点分别连线，新加线段数恰好是 3。

当然 p_4 也可以在外面，那将会带来两种情况：

在这种情况里，p_4 是合法的，因为它可以看见全部三个点，并分别连线。

如果是这种情况，p_4 很遗憾看不到 p_3​ 导致只能加两条边，这种情况是非法的。

画出多种情况后，我们很容易看出来，所有合法的情况里，都有一个最大的三角形包含了所有的点。

此外，整个大三角形内部会被分割为一个个三角形。

对于所有的 p_i，加入的情况都是类似的，总结一下，若 p_i 在最大三角形里面，p_i 一定位于一个内接三角形，连边就好了。

否则，判断能不能形成新的大三角形包含所有点，可以，就和大三角形的三个点连边，不行，则为不合法的情况。

具体实现

我们先考虑最重要的操作之一，如何判断一个点是否在三角形内？

对于这个问题，我们可以判断新连边后切割出来的新的三角形的面积之和与原本三角形面积的大小关系，只有相等时点在三角形内。

三角形面积用向量处理，公式很简单：S=\frac{|x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)|}2。

同时我们要用 \Theta(n^4) 的复杂度预处理出 w_{i,j,k}(i<j<k)，为 i,j,k 三点为最大三角形的三个顶点，在大三角形外的点的数量。

我们设 dp_{i,j,k}(i<j<k) 为，i,j,k 老样子，目前我们处理完了三角形外的点后的方案数。

计算答案我们可以考虑倒序处理这个问题，因为，我们发现，最终的所有点都应该被包含在一个最大的三角形里，否则答案为 0！

那我们记录下所有的三角形三元组，按照 w 从小到大排序，然后依次处理答案。

初值只需要找到第一个三元组 x,y,z，也就是最大的三角形，dp_{x,y,z}=1。

现在我们考虑转移：

设现在的三角形是 i,j,k，找到一个 l，要求 l 位于三角形内。

首先，l 可以和 i,j,k 中任意两个组合，形成三种新的三角形，假设我们选择处理 i,j,l(i<j<l)，记得大小关系可能会发生改变，所以要排序。

先给式子：dp_{i,j,l}=dp_{i,j,l}+P(w_{i,j,l}-1,w_{i,j,l}-w_{i,j,k}-1)\times dp_{i,j,k}。

其中我们定义 P(a,b)=\frac{a!}{(a-b)!}，自然是 a 个数中选取 b 个的排列方案数。

解释一下式子，我们现在要将 i,j,l 外面的点提前选掉，去掉点 k，总共有 w_{i,j,l}-1 个，而现在我们新加了 w_{i,j,l}-w_{i,j,k}-1 个。

这新的 w_{i,j,l}-w_{i,j,k}-1 个点可以是 w_{i,j,l}-1 个点中任选的位置，所以有 P(w_{i,j,l}-1,w_{i,j,l}-w_{i,j,k}-1) 种方案数，点 k 一定最后选。

对于 i,l,k 和 l,j,k 也是一样的方法。

最后，对于一个 i,j,k，我们可以更新答案！

式子：ans=ans+6\times dp_{i,j,k}\times P(n-3,n-w_{i,j,k}-3)。

怎么说？我们定 i,j,k 为 p_1,p_2,p_3，那首先 i,j,k 可以有 6 种排列方法，其次，在 i,j,k 内的点要在 n-3 个点中选择位置，所以还要乘方案数。

记得取模！时间复杂度 \Theta(n^4)。

完结撒花(●'◡'●)

参考代码

#include<bits/stdc++.h>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
typedef long long ll;
using namespace std;
const int N=51,d=1e9+7;
int n,dp[N][N][N],a[N],b[N],w[N][N][N],f,x,y,z,s[N]={1},t[N],cnt,ans,o[5];
struct tri
{
    int a,b,c;
}tr[N*N*N];
int calc(int i,int j,int k)//计算面积
{
    int v=abs(a[i]*(b[j]-b[k])+a[j]*(b[k]-b[i])+a[k]*(b[i]-b[j]));
    return v;
}
int check(int i,int j,int k,int l)//判断是否在三角新内
{
    if(calc(i,j,l)+calc(i,k,l)+calc(j,k,l)==calc(i,j,k))
      return 1;
    return 0;
}
int quickpow(int b,int p)
{
    int w=1;
    while(p)
    {
        if(p&1)
          w=1ll*w*b%d;
        b=1ll*b*b%d;
        p=p>>1;
    }
    return w;
}
int P(int x,int y)//排列方案数
{
    int v=1ll*s[x]*t[x-y]%d;
    return v;
}
bool cmp(tri x,tri y)
{
    return w[x.a][x.b][x.c]<w[y.a][y.b][y.c];
}
int main()
{
    int i,j,k,l;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
      scanf("%d%d",a+i,b+i),s[i]=1ll*s[i-1]*i%d;
    t[n]=quickpow(s[n],d-2);
    for(i=n;i;--i)
      t[i-1]=1ll*t[i]*i%d;
    for(i=1;i<=n;++i)//预处理w
    {
        for(j=i+1;j<=n;++j)
        {
            for(k=j+1;k<=n;++k)
            {
                ++cnt,tr[cnt]=(tri){i,j,k};
                for(l=1;l<=n;++l)
                {
                    if(!check(i,j,k,l))
                      ++w[i][j][k];
                }
                if(!w[i][j][k]&&!f)
                  x=i,y=j,z=k,f=1;
            }
        }
    }
    if(!f)
    {
        printf("0");
        return 0;
    }
    sort(tr+1,tr+cnt+1,cmp);//所有
    dp[x][y][z]=1;
    for(i=1;i<=cnt;++i)
    {
        x=tr[i].a,y=tr[i].b,z=tr[i].c;
        ans=(ans+6ll*P(n-3,n-w[x][y][z]-3)*dp[x][y][z]%d)%d;//算答案
        for(j=1;j<=n;++j)
        {
            if(j!=x&&j!=y&&j!=z&&check(x,y,z,j))
            {
                for(k=1;k<=3;++k)
                {
                    o[1]=x,o[2]=y,o[3]=z;
                    o[k]=j;//把新点塞进去
                    sort(o+1,o+4);//记得要满足大小关系
                    dp[o[1]][o[2]][o[3]]=(dp[o[1]][o[2]][o[3]]+1ll*P(w[o[1]][o[2]][o[3]]-1,w[o[1]][o[2]][o[3]]-w[x][y][z]-1)*dp[x][y][z]%d)%d;//有点长的转移）
                }
            }
        }
    }
    printf("%d",ans); 
    return 0;
}