1 条题解

  • 0
    @ 2026-11-15 19:27:39

    题目分析

    云(cloud)题解

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

    • 1

    信息

    ID
    178
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    1
    已通过
    1
    上传者