做it行业招标网站,国外网站设计欣赏,自己设计虚拟人物app,邢台专业网站建设PQ树
对于非叶子节点#xff0c;它只能调换它的儿子的顺序#xff0c;却不能调换整颗子树的顺序合法的PQ树都能表示出1,2,3,…,n 这个排列由以上两点可以得出#xff1a;PQ树的每棵子树对应的一定都是一段连续的数字区间考虑区间DP#xff0c;设f(l,r)f(l,r)f(l,r)表示数字…PQ树
对于非叶子节点它只能调换它的儿子的顺序却不能调换整颗子树的顺序合法的PQ树都能表示出1,2,3,…,n 这个排列由以上两点可以得出PQ树的每棵子树对应的一定都是一段连续的数字区间考虑区间DP设f(l,r)f(l,r)f(l,r)表示数字l~r构成一棵PQ树的方案数数字l~r 能够构成一棵子树 当且仅当 数字l~r 在题目给出的所有排列中都在一段连续区间中我们定义这样的 [l,r] 是“好的”若[l,r]不是好的f(l,r)0f(l,r)0f(l,r)0若[l,r]是好的要算f(l,r)f(l,r)f(l,r)分 树根为P点 和 树根为Q点 两种情况讨论若树根为P点f(l,r)∑ilr−1f(l,i)g(i1,r)f(l,r)\sum_{il}^{r-1}f(l,i)g(i1,r)f(l,r)∑ilr−1f(l,i)g(i1,r)其中g(i1,r)g(i1,r)g(i1,r)表示数字i1~r构成一片PQ树森林(可以只有一颗树) 的方案数g(l,r)f(l,r)∑ilr−1f(l,i)g(i1,r)g(l,r)f(l,r)\sum_{il}^{r-1}f(l,i)g(i1,r)g(l,r)f(l,r)∑ilr−1f(l,i)g(i1,r)注意这里并不要求[l,r]是“好的”若树根为Q点 f(l,r)∑ilr−1[在题目给出的排列中数字i,i1,r出现的位置均满足单调递增或递减]f(l,i)q(i1,r)f(l,r)\sum_{il}^{r-1}[在题目给出的排列中数字i,i1,r出现的位置均满足单调递增或递减]f(l,i)q(i1,r)f(l,r)∑ilr−1[在题目给出的排列中数字i,i1,r出现的位置均满足单调递增或递减]f(l,i)q(i1,r) q(i1,r)q(i1,r)q(i1,r)表示数字i1~r构成Q节点下除第一棵子树外的其它子树(至少2棵) 的方案数 ps:因为数字i,i1,r一定分属3棵子树所以它们的位置关系可以代表其所在子树的位置关系 q(l,r)∑ilr−1f(l,i)(f(i1,r)[在题目给出的排列中数字i,i1,r出现的位置均满足单调递增或递减]q(i1,r))q(l,r)\sum_{il}^{r-1}f(l,i)(f(i1,r)[在题目给出的排列中数字i,i1,r出现的位置均满足单调递增或递减]q(i1,r))q(l,r)∑ilr−1f(l,i)(f(i1,r)[在题目给出的排列中数字i,i1,r出现的位置均满足单调递增或递减]q(i1,r)) ps:这里在实现上有一个小技巧与其在dp时不断判断 数字i,i1,r出现的位置是否满足单调递增或递减 我们在求q时就把这个条件加进去即若 某排列中数字l-1l,l,r出现的位置不满足单调递增或递减直接令q(l,r)0q(l,r)0q(l,r)0 pps:关于转移式如何推出——其实我们计算f,g,qf,g,qf,g,q的基本方法都是枚举第一棵子树然后讨论剩余子树的情况
#includeiostream
#includecstdio
#includecstring
using namespace std;
typedef long long ll;
const int N510;
const ll mod1e97;
int K,n,a[N][N],pos[N][N],num[N][N];
bool ok[N][N];
ll f[N][N],g[N][N],q[N][N];
//f[l][r]:数l~r构成一棵PQ树的方案数
//g[l][r]:数l~r构成一片PQ树森林的方案数可以只有一棵树
//q[l][r]:数l~r构成Q节点下除第一棵子树外的其它子树 的方案数
void pre(){for(int i1;iK;i){for(int j1;jn;j){int minna[i][j],maxna[i][j];for(int kj;kn;k){minnmin(minn,a[i][k]);maxnmax(maxn,a[i][k]);if(k-jmaxn-minn){//排列i中区间[j,k]里的数是连续的num[minn][maxn];//即区间[j,k]里的数在排列i中属于一段连续区间 } }}}for(int i1;in;i)for(int ji;jn;j)ok[i][j](num[i][j]K);
}
ll F(int l,int r);
ll G(int l,int r);
ll Q(int l,int r);
ll F(int l,int r){if(!ok[l][r]) return 0;if(lr) return 1;if(f[l][r]!-1) return f[l][r];f[l][r]0;for(int il;ir;i){f[l][r](f[l][r]F(l,i)*G(i1,r)%mod)%mod;//树根是P节点 f[l][r](f[l][r]F(l,i)*Q(i1,r)%mod)%mod;//树根是Q节点 }return f[l][r];
}
ll G(int l,int r){if(lr) return 0;if(lr) return 1;if(g[l][r]!-1) return g[l][r];g[l][r]F(l,r);for(int il;ir;i){g[l][r](g[l][r]F(l,i)*G(i1,r)%mod)%mod;}return g[l][r];
}
ll Q(int l,int r){if(lr) return 0;if(q[l][r]!-1) return q[l][r];for(int i1;iK;i){if((pos[i][l-1]pos[i][l])^(pos[i][l]pos[i][r])){q[l][r]0;return 0;}}q[l][r]0;for(int il;ir;i){q[l][r](q[l][r]F(l,i)*((Q(i1,r)F(i1,r))%mod)%mod)%mod;}return q[l][r];
}
int main(){scanf(%d%d,K,n);for(int i1;iK;i){for(int j1;jn;j){scanf(%d,a[i][j]);pos[i][a[i][j]]j;}}pre();memset(f,-1,sizeof(f));memset(g,-1,sizeof(g));memset(q,-1,sizeof(q));printf(%d\n,F(1,n));return 0;
}
