首页 > 其他 > 详细

51nod 1934 受限制的排列——笛卡尔树

时间:2019-02-24 17:19:28      阅读:158      评论:0      收藏:0      [点我收藏+]

题目:http://www.51nod.com/Challenge/Problem.html#!#problemId=1934

根据给出的信息,可以递归地把笛卡尔树建出来。一个点只应该有 0/1/2 个孩子,不然就是无解。

dp[ cr ] 表示把 1~siz[cr] 填进 cr 这个子树的方案数。那么 \( dp[cr]=C_{siz[cr]-1}^{siz[ls]}*dp[ls]*dp[rs] \) 。

注意在各种地方判断无解!如果是 l , cr , r 的话,左孩子应该是 l , ls , cr-1 ,右孩子应该是 cr+1 , rs , r 这样的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#define ls Ls[cr]
#define rs Rs[cr]
#define pb push_back
#define ll long long
using namespace std;
int rdn()
{
  int ret=0;bool fx=1;char ch=getchar();
  while(ch>9||ch<0){if(ch==-)fx=0;ch=getchar();}
  while(ch>=0&&ch<=9)ret=ret*10+ch-0,ch=getchar();
  return fx?ret:-ret;
}

const int N=1e6+5,mod=1e9+7;
int pw(int x,int k)
{int ret=1;while(k){if(k&1)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=1;}return ret;}

int n,rt,l[N],Ls[N],Rs[N],siz[N],dp[N],jc[N],jcn[N]; bool flag;
struct Node{
  int r,p;
  Node(int r=0,int p=0):r(r),p(p) {}
  bool operator< (const Node &b)const
  {return r<b.r;}
};
vector<Node> st[N];
vector<int> vt[N];
void init()
{
  int n=1e6;
  jc[0]=1;for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%mod;
  jcn[n]=pw(jc[n],mod-2);
  for(int i=n-1;i>=0;i--)jcn[i]=(ll)jcn[i+1]*(i+1)%mod;
}
int C(int n,int m)
{return (ll)jc[n]*jcn[m]%mod*jcn[n-m]%mod;}
void solve(int L,int R,int cr)
{
  int tl=L,v,tr;
  vt[cr].clear();//
  if(cr>L)
    {
      if(!l[L]){flag=1;return;}
      Node v=st[L][--l[L]]; int bh=v.p;
      if(v.r!=cr-1){flag=1;return;}
      solve(L,cr-1,bh); if(flag)return;
      ls=bh;
    }
  else ls=0;
  if(cr<R)
    {
      if(!l[cr+1]){flag=1;return;}
      Node v=st[cr+1][--l[cr+1]]; int bh=v.p;
      if(v.r!=R){flag=1;return;}
      solve(cr+1,R,bh); if(flag)return;
      rs=bh;
    }
  else rs=0;
  siz[cr]=siz[ls]+siz[rs]+1;
  dp[cr]=(ll)C(siz[cr]-1,siz[ls])*dp[ls]%mod*dp[rs]%mod;
}
int main()
{
  int T=0; init(); dp[0]=1;//
  while(scanf("%d",&n)==1)
    {
      for(int i=1;i<=n;i++)st[i].clear();//
      for(int i=1;i<=n;i++)l[i]=rdn();
      for(int i=1,r;i<=n;i++)
    {
      r=rdn();st[l[i]].pb(Node(r,i));
    }
      for(int i=1;i<=n;i++)
    {
      sort(st[i].begin(),st[i].end());
      l[i]=st[i].size();
    }
      T++; printf("Case #%d: ",T);
      if(!l[1])puts("0");
      else
    {
      Node rt=st[1][--l[1]]; int bh=rt.p;
      if(rt.r!=n)puts("0");
      else {flag=0; solve(1,n,bh); printf("%d\n",flag?0:dp[bh]);}
    }
    }
  return 0;
}

 

51nod 1934 受限制的排列——笛卡尔树

原文:https://www.cnblogs.com/Narh/p/10426823.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!