计数(count)

题目描述

既然是萌萌哒 visit_world 的比赛，那必然会有一道计数题啦！

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

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

现在，给出MM个限制条件，第ii个限制条件给出了ui,viui,vi，表示Aui<AviAui<Avi ，也即中序遍历中uiui在vivi 之前出现.

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

输入

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

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

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

输出

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

样例输入

样例输出

提示

解释

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

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

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

样例 2

见下发文件.

数据范围和子任务

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

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

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

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

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

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

来源

hnsdfz国庆集训day2

solution

20分是卡特兰数然后我打崩了

令f[i][j]表示先序遍历序号为i~j的组成的树有多少种不同形态

那么 if(合法) f[i][j]=f[i+1][k]+f[k+1][j]

我们考虑怎么判断一个点是否合法

那么

1 [i+1,k]的任何一个点中序遍历都不能在[k+1,j] 以后

2 [i+1,k]的任何一个点中序遍历都不能在i以后

3 i的中序遍历都不能在[k+1,j] 以后

区间对区间可以用二维前缀和优化

效率O（n^3）

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 405
#define mod 1000000007
#define ll long long
using namespace std;
int T,n,m,t1,t2;
ll f[maxn][maxn],s[maxn][maxn],a[maxn][maxn];
void init(){
    for(int i=0;i<=400;i++)
    for(int j=0;j<=400;j++)f[i][j]=s[i][j]=a[i][j]=0;
}
int calc(int x,int y,int xx,int yy){
    return s[xx][yy]-s[xx][y-1]-s[x-1][yy]+s[x-1][y-1];
}
bool pd(int ii,int xa,int xb,int ya,int yb){
    if(calc(ya,xa,yb,xb))return 0;
    if(calc(ya,ii,yb,ii))return 0;
    if(calc(ii,xa,ii,xb))return 0;
    return 1;
}
int main()
{
    cin>>T;
    while(T--){
        init();
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&t1,&t2);
            a[t1][t2]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
        for(int i=1;i<=n;i++)f[i][i]=1;
        for(int l=1;l<=n;l++){
        for(int i=1;i+l<=n;i++){
            int j=i+l;
            if(!calc(i,i+1,i,j))f[i][j]+=f[i+1][j];
            if(!calc(i+1,i,j,i))f[i][j]+=f[i+1][j];
            for(int k=i+1;k<j;k++){
                if(pd(i,i+1,k,k+1,j)){
                    f[i][j]+=f[i+1][k]*f[k+1][j];
                     
                }
             
                f[i][j]%=mod;
            }
          }
        }
        cout<<f[1][n]<<endl;
    }
    return 0;
}