首页 > 其他分享 >一棵有根树的拓扑排序数量

一棵有根树的拓扑排序数量

时间:2023-07-21 16:35:36浏览次数:27  
标签:prod 拓扑 Son 序列 子树 根树 排序 sum

今日见到一个有趣的问题,就是本篇的题目。
这里可以把它看作一个dp问题,\(f_i\)表示以\(i\)为根节点的子树的拓扑排序数量,要求出\(f_i\),就要知道\(f_j\) (\(j\in Son_i\)),但是它不是处理完一个子树,再处理另一个子树,它是穿插着来的,所以这个问题就变成了,已知\(k\)个序列,问有多少序列满足这\(k\)个序列中任意序列在新序列中顺序不变。
这里可以先看一个新问题,有\(n\)种数,第\(i\)种数有\(a_i\)个,问所有数能组成多少种序列?
这个问题的答案就是$\frac{(\sum_{i=1}^{n} a_i)!}{\prod_{i=1}^{n} (a_i!)} $。
这里可以发现这个问题和我们想求的问题其实是一样的,所以这里可以得出式子 \(f_i=\frac{(\sum_{j\in Son_i} sum_j-1)!}{\prod_{j\in Son_i} (sum_j!)} \times \prod_{j\in Son_i} f_j\)。

标签:prod,拓扑,Son,序列,子树,根树,排序,sum
From: https://www.cnblogs.com/z-2-we/p/17571780.html

相关文章

  • mysql 根据in 传参排序
    MySQL根据IN传参排序在MySQL中,我们经常需要根据给定的一组值来进行排序操作。而IN关键字正是用来筛选出一组指定值的数据。本文将详细介绍如何在MySQL中使用IN传参进行排序。什么是IN关键字IN关键字是MySQL中的一个操作符,用于指定一个值是否在一个指定的范围内。其基本语法如下:......
  • mysql分页后排序失效数据丢失解决方案
    mysql使用Limit分页不加索引列会导致数据丢失、重复和索引失效mysql官网对limit的详细说明及优化建议:https://dev.mysql.com/doc/refman/5.7/en/limit-optimization.html官网IfmultiplerowshaveidenticalvaluesintheORDERBYcolumns,theserverisfreetoreturnt......
  • 两个字段相加的值排序 mysql
    实现“两个字段相加的值排序mysql”介绍在MySQL数据库中,我们经常会遇到需要对两个字段相加的值进行排序的需求。这个过程可以通过使用MySQL的ORDERBY语句来实现。在本文中,我将指导你实现这个功能的步骤,并提供相应的代码示例。实现步骤下面是实现“两个字段相加的值排序mysql......
  • java map 自定义排序key value
    JavaMap自定义排序KeyValue在Java中,Map是一种经常用到的数据结构,它提供了一个存储键值对的集合。默认情况下,Map中的元素是按照插入顺序进行排序的。然而,在某些情况下,我们可能需要按照自定义的方式对Map进行排序,本文将介绍如何在Java中自定义排序Map的Key和Value......
  • java中list从大到小排序方法
    Java中List从大到小排序方法在Java中,List是一种常用的数据结构,可以存储一组有序的元素。有时候我们需要对List中的元素进行排序操作,常见的排序方式有从小到大和从大到小两种。本文将介绍如何使用Java中的Collections类和Comparator接口来实现List从大到小的排序。Collections类的......
  • java则么对list进行排序
    如何使用Java对List进行排序引言在Java开发中,我们经常需要对列表进行排序。排序可以按照不同的标准进行,例如按照数字大小、字符串字母顺序等。本文将向你介绍如何使用Java对List进行排序,以及每一步骤的具体操作和代码示例。流程概述下面是对List排序的一般流程的概述,我们将通过......
  • mysql 自定义排序
    MySQL自定义排序的实现概述在MySQL中,我们可以通过自定义排序来按照自己的需求对查询结果进行排序。自定义排序可以用于对某一列进行特殊排序,例如按照指定的顺序或者特定的规则排序。本文将详细介绍在MySQL中实现自定义排序的步骤和代码示例。流程下面是实现MySQL自定义排序的基......
  • el-table表格行拖拽排序或者电子件列表拖拽排序
    用到sortablejs 中文官网,http://www.sortablejs.com/为了页面中可以复用,在common.js下,封装了公用方法import Sortable from‘sortablejs’rowDrop(selector,params,callback){lettbody=document.querySelector(selector)if(!tbody){return}if(window.tableSortab......
  • python 按文件时间戳 排序
    Python按文件时间戳排序简介在开发过程中,我们经常会遇到需要按照文件的时间戳进行排序的需求。Python提供了丰富的模块和方法来处理文件操作和时间戳,使得这个任务变得非常简单。本文将引导你完成按照文件时间戳排序的过程,并提供相应的代码示例。流程以下是按照文件时间戳排序的......
  • 快速排序
    快速排序主要思想快速排序所采用的思想是分治的思想。所谓分治,就是指以一个数为基准,将序列中的其他数往它两边“扔”。以从小到大排序为例,比它小的都“扔”到它的左边,比它大的都“扔”到它的右边,然后左右两边再分别重复这个操作,不停地分,直至分到每一个分区的基准数的左边或者右......