资讯详情

• 11.3
  • 考虑要以 \(x\) 为端需要的操作次数为 \(n - 3\) - 以 \(x\) 为端的个数
  • 考虑方案数
    • 如果有 \((x,p),(x,q),(p,q)\) 那一定存在一个 \(r\) 有 \((p,r),(q,r)\) 则可以把 \((p,q)\) 变成 \((x,r)\)
    • 将所有对角线写成不经过 \(x\) 的弧的形式
      • 任意两个弧要么包含要么交的长度为 0
      • 每次操作都是选择一个不被别的弧包含的弧（极大弧），并删去
      • 考虑 \((p,q)\) 被删去后会产生 \((p,r),(r,q)\) 这两条可删去的弧
      • 我们可以把这个东西看成一个树形结构
    • 故我们可以把问题转换为求取森林的拓扑序数量
    • 一棵 \(m\) 个点的森林的拓扑序的数量即为 \(\frac{m!}{\prod\limits_{i} siz_i}\) , 这里的 \(m\) 即为两端均不为 \(x\) 的对角线数量
      • 考虑 \(l-r\) 的弧的子树大小为 \(r-l-1\)
    • 故考虑修改操作是区间乘，即可用线段树维护

• 11.4