信息
- ID
- 178
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
两种顺序的不同之处只在于同行的棋子的顺序是反着来的。根据这个可以有不同的做法,我们只讲其中一种:记 pi 表示 ai 在 b 中的出现位置,那么 p 序列的每个极长下降段便标识了同行的棋子,对于一个极长下降段 [l,r],a[l,r] 和 b[l,r] 应该是反序的关系,判断一下,如果不是反序就没有可行方案。这样我们会分出若干段,如果段数超过了 n 也没有可行方案,否则相当于先从 n 行里选出若干行,行内再进行放置,用组合数算一下方案数即可。这里只需要用到递推 C(n,m)=C(n−1,m−1)+C(n−1,m)。