[学习笔记]卡特兰数/Prufer序列

1. 卡特兰数

卡特兰数常出现于组合数学/计数问题中

卡特兰数的前 $20$ 项是：$$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, $$ $$16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190$$

卡特兰数的通项公式是：（记第 $n$ 项卡特兰数为 $Cat_n$ ）

$$Cat_n=/dfrac{C_{2n}^n}{n+1}$$

此外，卡特兰数还满足以下关系：

$$Cat_{n+1}=/sum/limits_{i=0}^{n}Cat_i/times Cat_{n-i}$$

卡特兰数可以用于解决以下问题：

$/qquad/mathfrak{1:}$ 一个长度为 $2n$ 的括号序列，合法的排列个数即为 $Cat_n$

$/qquad/qquad$ 譬如一个括号序列长度为 $6$ ，它的合法排列有

$$((())),(()()),()()(),(())(),()(())$$

$/qquad/qquad$ 一共 $Cat_3=5$ 种

$/qquad/mathfrak{2:}$ 一个长度为 $n$ 的序列，进出栈的不同方案数是 $Cat_n$

$/qquad/mathfrak{3:}$  凸 $n$ 边形三角划分，方案数是 $Cat_{n-1}$

$/qquad/mathfrak{4:}$ 给定 $n$ 个点，可以组成 $Cat_{n+1}$ 棵二叉搜索树

等等等等

卡特兰数的题目诡异在你不知道它是卡特兰数

比如 这道题目 就是一道很好的卡特兰数题

不妨设答案为 $f(n)$，这道题目可以考虑如下方法：

比如一个 $5$ 阶的楼梯，观察最左下角的方格如何被覆盖：

1. 被一个高为 $5$ 的方格覆盖，右边留下了一个 $4$ 阶的楼梯，方案数 $f(4)$
2. 被一个高 $4$ 宽 $2$ 的方格覆盖，此时留下了上面的 $1$ 阶楼梯和右边的 $3$ 阶楼梯，方案数 $f(3)$
3. 被一个高 $3$ 宽 $3$ 的方格覆盖，类似的，方案数 $f(2)/times f(2)$
4. 被一个高 $2$ 宽 $4$ 的方格覆盖，方案数 $f(3)$
5. 被一个宽为 $5$ 的长条覆盖，方案数显然是 $f(4)$

分类讨论结束，发现 $f(0)=f(1)=1$

也就是说 $f(5)=/sum/limits_{i=0}^{4}f(i)/times f(4-i)$，也就是卡特兰数

需要使用高精度

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000,INF=1099511627776,mod=1e6;
struct BigNum{
    int num[1010],len;
    void clr(){memset(num,0,sizeof(num));len=0;}
    BigNum operator =(int val){
        clr();
        while(val){
            num[++len]=val%mod;
            val/=mod;
        }
        return *this;
    }
    bool operator <(const BigNum &b)const{
        if(len!=b.len) return len<b.len;
        for(int i=len;i>=1;i--){
            if(num[i]!=b.num[i]) return num[i]<b.num[i];
        }
        return false;
    }
    bool operator >(const BigNum &b)const{
        if(len!=b.len) return len>b.len;
        for(int i=len;i>=1;i--){
            if(num[i]!=b.num[i]) return num[i]>b.num[i];
        }
        return false;
    }
    bool operator ==(const BigNum &b)const{
        if(len!=b.len) return false;
        for(int i=len;i>=1;i--){
            if(num[i]!=b.num[i]) return false;
        }
        return true;
    }
    bool operator !=(const BigNum &b)const{
        if(len!=b.len) return true;
        for(int i=len;i>=1;i--){
            if(num[i]!=b.num[i]) return true;
        }
        return false;
    }
    bool operator >=(const BigNum &b)const{return (b==*this||b>*this);}
    bool operator <=(const BigNum &b)const{return (b==*this||b<*this);}
    BigNum operator +(const int &b)const{
        BigNum res=*this;
        res.num[1]+=b;
        for(int i=1;i<=res.len;i++){
            if(!res.num[i]/mod) break;
            res.num[i+1]+=res.num[i]/mod;
            res.num[i]%=mod;
        }
        while(res.num[++res.len]){
            res.num[res.len+1]+=res.num[res.len]/mod;
            res.num[res.len]%=mod;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        return res;
    }
    BigNum operator +(const BigNum &b)const{
        BigNum res=*this;
        for(int i=1;i<=b.len;i++){
            res.num[i]+=b.num[i];
            res.num[i+1]+=res.num[i]/mod;
            res.num[i]%=mod;
        }
        while(res.num[++res.len]){
            res.num[res.len+1]+=res.num[res.len]/mod;
            res.num[res.len]%=mod;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        return res;
    }
    BigNum operator +=(const BigNum &b){*this=*this+b;return *this;}
    BigNum operator +=(const int &b){*this=*this+b;return *this;}
    BigNum operator -(const int &b)const{
        BigNum res=*this;
        res.num[1]-=b;
        for(int i=1;i<=res.len;i++){
            if(res.num[i]<0) res.num[i]+=mod,res.num[i+1]--;
            else break;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        return res;
    }
    BigNum operator -(const BigNum &b)const{
        BigNum res=*this;
        for(int i=1;i<=b.len;i++){
            res.num[i]-=b.num[i];
            if(res.num[i]<0) res.num[i]+=mod,res.num[i+1]--;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        return res;
    }
    BigNum operator -=(const BigNum &b){*this=*this-b;return *this;}
    BigNum operator -=(const int &b){*this=*this-b;return *this;}
    BigNum operator *(const int &b)const{
        BigNum res=*this;
        for(int i=1;i<=res.len;i++) res.num[i]*=b;
        for(int i=1;i<=res.len;i++){
            res.num[i+1]+=res.num[i]/mod;
            res.num[i]%=mod;
        }
        while(res.num[++res.len]){
            res.num[res.len+1]+=res.num[res.len]/mod;
            res.num[res.len]%=mod;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        return res;
    }
    BigNum operator *(const BigNum &b)const{
        BigNum res;res.clr();
        for(int i=1;i<=len;i++){
            for(int j=1;j<=b.len;j++){
                res.num[i+j-1]+=num[i]*b.num[j];
                res.num[i+j]+=res.num[i+j-1]/mod;
                res.num[i+j-1]%=mod;
            }
        }
        res.len=len+b.len;
        while(res.num[++res.len]){
            res.num[res.len+1]+=res.num[res.len]/mod;
            res.num[res.len]%=mod;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        return res;
    }
    BigNum operator *=(const BigNum &b){*this=*this*b;return *this;}
    BigNum operator *=(const int &b){*this=*this*b;return *this;}
    BigNum operator /(const int &b)const{
        BigNum res=*this;
        int bin;
        for(int i=res.len;i>=1;i--){
            res.num[i]=(bin*mod+num[i])/b;
            bin=(bin*mod+num[i])%b;
        }
        while(res.len>1&&!res.num[res.len]) res.len--;
        // res.print();
        // putchar('/n');
        return res; 
    }
    BigNum operator /=(const int &b){*this=*this/b;return *this;}
    // void numcopy(BigNum &b,int det)const{
    //     for(int i=1;i<=len;i++){
    //         b.num[i+det-1]=num[i];
    //     }
    // }
    // BigNum operator /(const BigNum &b)const{
    //     BigNum res=*this,tmp;
    //     res.len=max((int)1,len-b.len+1);
    //     for(int i=res.len;i>=1;i--){
    //         tmp.clr();

    //     }
    // }
    void print(){
        printf("%lld",num[len]);
        for(int i=len-1;i>=1;i--){
            if(!len) break;
            printf("%06lld",num[i]);
        }
    }
};
int n,m;
int prime[WR],mind[WR],tot;
int cnt[WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void sieve(){
    for(int i=2;i<WR;i++){
        if(!mind[i]) mind[i]=i,prime[++tot]=i;
        for(int j=1;i*prime[j]<WR&&j<=tot;j++){
            if(prime[j]>mind[i]) break;
            mind[i*prime[j]]=prime[j];
        } 
    }
}
void add(int num){
    while(num^1){
        cnt[mind[num]]++;
        num/=mind[num];
    }
}
void del(int num){
    while(num^1){
        cnt[mind[num]]--;
        num/=mind[num];
    }
}
BigNum quick_pow(int a,int b){
    BigNum base,res;
    base=a,res=(int)1;
    while(b){
        if(b&1) res=res*base;
        base=base*base;
        b>>=1;
    }
    return res;
}
BigNum comb(int n,int m){
    BigNum res;
    res=(int)1;
    memset(cnt,0,sizeof(cnt));
    for(int i=m+1;i<=n;i++) add(i);
    for(int i=1;i<=n-m;i++) del(i);
    for(int i=1;i<=tot;i++) res=res*quick_pow(prime[i],cnt[prime[i]]);
    return res;
}
signed main(){
    sieve();
    n=read();
    BigNum ans;
    ans=comb(n*2,n);
    // ans.print();
    // putchar('/n');
    ans/=(n+1);
    ans.print();
    return 0;
}

View Code

 

还可以看一下这里的 $C$ 题

 

2. Prufer序列

$/operatorname{Prufer}$ 序列可以将一个带标号 $n$ 个结点的树用 $[1,n]$ 中的 $n-2$ 个整数表示。

你也可以把它理解为完全图的生成树与数列之间的双射。

$/operatorname{Prufer}$ 序列是这样建立的：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。

重复 $n-2$ 次后就只剩下两个结点，算法结束。

 考虑下图的这棵树

 

 

 

我们需要重复进行以下操作，直至树中只剩下两个点：

• 找到一个度数为 $1$ ，且编号最小的点。（其中编号最小保证了后面将会提到的 $/operatorname{Prufer}$ 序列的唯一对应性，同时也方便了 $/operatorname{Prufer}$ 序列向无根树的转化
• 把这个点的父亲节点加入序列，然后把这个点从树中删除。

结束了。

以上图为例：

1. 度为 $1$ 的点为 ${4,5,6,7}$，将最小的点 $4$ 删除，将连接 $4$ 号节点的 $2$ 号节点加入 $/operatorname{Prufer}$ 序列，序列为 ${2}$
2. 继续将 $5$ 号节点删去，将 $3$ 号节点加入序列，发现 $3$ 号节点成为叶子节点，加入候选点集
3. 将 $3$ 号节点删去，加入 $1$ 号节点，序列变成 ${2,3,1}$
4. 候选点集中仅有 ${6,7}$ 两个节点，删除 $6$ ，加入 $2$
5. $2$ 进入候选点集，删除 $2$，加入 $1$，序列现在是 ${2,3,1,2,1}$

仅剩 $2$ 个节点，构造结束， $/operatorname{Prufer}$ 序列为 ${2,3,1,2,1}$

$/Theta (n/log n)$ 和 $/Theta(n)$ 构建代码（摘自 $OIwiki$ ）

vector<vector<int>> adj;

vector<int> pruefer_code() {
  int n = adj.size();
  set<int> leafs;
  vector<int> degree(n);
  vector<bool> killed(n, false);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1) leafs.insert(i);
  }

  vector<int> code(n - 2);
  for (int i = 0; i < n - 2; i++) {
    int leaf = *leafs.begin();
    leafs.erase(leafs.begin());
    killed[leaf] = true;
    int v;
    for (int u : adj[leaf])
      if (!killed[u]) v = u;
    code[i] = v;
    if (--degree[v] == 1) leafs.insert(v);
  }
  return code;
}

$/Theta(n/log n)$

// C++ Version
// 从原文摘的代码，同样以 0 为起点
vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
  for (int u : adj[v]) {
    if (u != parent[v]) parent[u] = v, dfs(u);
  }
}

vector<int> pruefer_code() {
  int n = adj.size();
  parent.resize(n), parent[n - 1] = -1;
  dfs(n - 1);

  int ptr = -1;
  vector<int> degree(n);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1 && ptr == -1) ptr = i;
  }

  vector<int> code(n - 2);
  int leaf = ptr;
  for (int i = 0; i < n - 2; i++) {
    int next = parent[leaf];
    code[i] = next;
    if (--degree[next] == 1 && next < ptr) {
      leaf = next;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  return code;
}$$$

vector<vector<int>> adj;
vector<int> parent;

void dfs(int v) {
  for (int u : adj[v]) {
    if (u != parent[v]) parent[u] = v, dfs(u);
  }
}

vector<int> pruefer_code() {
  int n = adj.size();
  parent.resize(n), parent[n - 1] = -1;
  dfs(n - 1);

  int ptr = -1;
  vector<int> degree(n);
  for (int i = 0; i < n; i++) {
    degree[i] = adj[i].size();
    if (degree[i] == 1 && ptr == -1) ptr = i;
  }

  vector<int> code(n - 2);
  int leaf = ptr;
  for (int i = 0; i < n - 2; i++) {
    int next = parent[leaf];
    code[i] = next;
    if (--degree[next] == 1 && next < ptr) {
      leaf = next;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  return code;
}

$/Theta(n)$

那么该如何从 $/operatorname{Prufer}$ 序列重构一棵树呢？

我们需要重复进行以下操作，直至点集中只剩下两个点：（初始化所有点都在点集中）

• 取出队列最前面的元素 $u$
• 取出在点集中，且当前不在 $/operatorname{Prufer}$ 序列中的最小编号点 $v$
• 在 $u$ 和 $v$ 间连边

还是以上图为例，我们有了一个序列叫做 $2,3,1,2,1$，点集是 $1,2,3,4,5,6,7$

考虑构造出 $/operatorname{Prufer}$ 序列对应的树

1. 取出序列中的 $2$ 和点集中的 $4$，连边
2. 依次取出 $3,5$、$1,3$、$2,6$、$1,2$ 连边
3. 此时点集中剩下了 $1,7$ ，将这两个连边即可复原

复原代码（同样摘自 $OIwiki$ ）

vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
  int n = code.size() + 2;
  vector<int> degree(n, 1);
  for (int i : code) degree[i]++;

  set<int> leaves;
  for (int i = 0; i < n; i++)
    if (degree[i] == 1) leaves.insert(i);

  vector<pair<int, int>> edges;
  for (int v : code) {
    int leaf = *leaves.begin();
    leaves.erase(leaves.begin());

    edges.emplace_back(leaf, v);
    if (--degree[v] == 1) leaves.insert(v);
  }
  edges.emplace_back(*leaves.begin(), n - 1);
  return edges;
}

$/Theta(n/log n)$

vector<pair<int, int>> pruefer_decode(vector<int> const& code) {
  int n = code.size() + 2;
  vector<int> degree(n, 1);
  for (int i : code) degree[i]++;

  int ptr = 0;
  while (degree[ptr] != 1) ptr++;
  int leaf = ptr;

  vector<pair<int, int>> edges;
  for (int v : code) {
    edges.emplace_back(leaf, v);
    if (--degree[v] == 1 && v < ptr) {
      leaf = v;
    } else {
      ptr++;
      while (degree[ptr] != 1) ptr++;
      leaf = ptr;
    }
  }
  edges.emplace_back(leaf, n - 1);
  return edges;
}

$/Theta(n)$
然后该说说 $/operatorname{Prufer}$ 序列的一些性质了

$/quad/mathfrak{1:}$ $/operatorname{Prufer}$ 序列和无根树一一对应

$/quad/mathfrak{2:}$ 度数为 $d_i$ 的节点会在 $/operatorname{Prufer}$ 序列中出现 $i-1$ 次

$/quad/mathfrak{3:}$ 一个 $n$ 个节点的完全图，生成树个数为 $n^{n-2}$（也叫 $Cayley$ 公式）

$/quad/mathfrak{4:}$ 对于一棵给定度数 $d_i$ 的无根树，共有 $/dfrac{(n-2)!}{/prod/limits_{i-1}^{n}(d_i-1)!}$ 种不同的树

有一道比较优秀的题目：这里

用到了性质 $/mathfrak{4}$，硬求解即可

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=200;
int n,sum;
int ans,d[WR];
int comb[WR][WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
signed main(){
    n=read();
    for(int i=0;i<=n;i++){
        comb[i][0]=1;
        for(int j=1;j<=i;j++){
            comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++) d[i]=read();
    if(n==1){
        if(!d[1]) printf("1/n");
        else printf("0/n");
        return 0;
    }
    for(int i=1;i<=n;i++){
        d[i]--;
        sum+=d[i];
    }
    if(sum!=n-2){
        printf("0/n");
        return 0;
    }
    sum=0,ans=1;
    for(int i=1;i<=n;i++){
        ans*=comb[n-2-sum][d[i]];
        sum+=d[i];
    }
    printf("%llu/n",ans);
    return 0;
}

View Code