【from new_dtoj 3967: 计数(count)】

题目描述

考虑一个 N个节点的二叉树，它的节点被标上了1∼N 的编号. 并且，编号为i的节点在二叉树的前序遍历中恰好是第i个出现.

我们定义Ai 表示编号为i的点在二叉树的中序遍历中出现的位置.

现在，给出M个限制条件，第i个限制条件给出了ui,vi，表示Aui<Avi ，也即中序遍历中ui在vi 之前出现.

你需要计算有多少种不同的带标号二叉树满足上述全部限制条件，答案对109{10^9}109+7 取模.

输入

第一行一个整数T(1≤T≤5), 表示数据组数.

每组数据第一行为两个整数N,M，意义如题目所述.

接下来M 行，每行两个整数ui,vi(1≤ui,vi≤N) . 描述一条限制.

输出

对每组数据，输出一行一个整数，表示答案.

样例输入

3

5 0

3 2

1 2

2 3

3 3

1 2

2 3

3 1

样例输出

42

1

0

提示

解释

第一组数据，无任何限制时，5 个点的二叉树形态个数为42 .

第二组数据，唯一满足条件的二叉树的形态为 1 - 2 - 3.（1 为根，2, 3 均为右儿子）.

第三组数据，限制条件产生矛盾.

数据范围和子任务

对于全部的测试数据，保证T≤5,N≤400,M≤103{10^3}103 .

子任务 1（20 分）：M=0 .

子任务 2（15 分）：N≤10 .

子任务 3（20 分）：N≤50,M≤1 .

子任务 4（15 分）：N≤50 .

子任务 5（30 分）：无特殊限制.

题解：

由于前序遍历是1-n，所以可以发现每一棵子树的dfs序是连续的，并且它的根是这棵子树内编号最小的点

所以设f[i][j]表示以i为一棵子树的根，这棵子树最大编号为j，能满足限制的答案值

明显若不考虑限制，f[i][j]=∑k=ijF(i+1,k)∗F(k+1,j)f[i][j]=\sum_{k=i}^{j}F(i+1,k)*F(k+1,j)f[i][j]=∑k=ij​F(i+1,k)∗F(k+1,j)

考虑限制，我们把一个限制看成二维平面上的一个点(ui,vi)，并且这个点的权值为1

那么当在顶点坐标为(k+1,i+1),(j,k);(i,i+1),(i,k);(k+1,i),(j,i)(左上和右下)内的和为0时，k是满足限制的，所以就完美解决啦

代码如下

#include 
    
     using namespace std;const int P=1e9+7;int T,n,m,f[405][405],s[405][405];bool calm(int l1,int r1,int l2,int r2){    if (r1
     
      
       =r) return f[l][r]=1;    if (~f[l][r]) return f[l][r];f[l][r]=0;    for (int i=l;i<=r;i++) if (judge(i+1,r,l+1,i))        f[l][r]=(1ll*f[l][r]+1ll*F(l+1,i)*F(i+1,r)%P)%P;    return f[l][r];}int main(){    for (scanf("%d",&T);T--;){        scanf("%d%d",&n,&m);        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[i][j]=0;        for (int x,y,i=1;i<=m;i++) scanf("%d%d",&x,&y),s[x][y]=1;        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1],f[i][j]=-1;        printf("%d\n",F(1,n));    }    return 0;}