RainAir
My OI Blog
RainAir
「JZOJ6395」消失的序列

题目描述

计数。有多少个长度为 $n$ 的排列,使得可以通过栈排好序并且第 $ps$ 个位置是 $x$。
$n \leq 10^6$

题解

首先我们考虑反过来:变成问你 $1 \cdots n$ 的排列通过栈可以生成多少在 $ps$ 位置为 $x$ 的序列。
考虑将这个过程抽象成括号序列:长度为 2n 的括号序列,左括号表示入栈,右括号表示出栈。
那么我们实际上是为了计数长度为 $2n$ 的括号序列,满足第 $ps$ 个左括号和第 $x$ 个右括号是配对在一起的。我们可以枚举左括号在哪里,就可以唯一确定右括号在哪里。分成了三个不同的括号序列都用卡特兰数算一算就好了。
大概是长得这样:
…….(…….)…….
首先 ( 和 ) 之间的左右括号数一定相等(也就是保证这两个括号匹配上)
我们枚举 ( 的位置是 $l$,可以轻易算出。(可以看代码)

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/940
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「JZOJ6395」消失的序列
题目描述 计数。有多少个长度为 $n$ 的排列,使得可以通过栈排好序并且第 $ps$ 个位置是 $x$。 $n \leq 10^6$ 题解 首先我们考虑反过来:变成问你 $1 \cdots n$ 的排列通过栈可以生成…
扫描二维码继续阅读
2019-11-02
标签
近期评论