1 条题解

  • 0
    @ 2026-11-15 19:21:48

    题目分析

    算法 1

    我会暴力!

    枚举 nn 的全排列,单次 O(n)O(n) 查询是否符合条件,累加即可。

    期望得分 5 分。

    算法 2

    期望得分 40 分。

    算法 3

    我会先猜结论然后证明!

    【结论】 令下标数列 {pm}(pi≠1)\{p_m\}(p_i\ne 1) 表示所有 bpi=0b_{p_i}=0,则答案为 ∏i=1m(pi−1)\prod_{i=1}^m(p_i-1)。

    【证明】 令 f(b,n)f(b,n) 表示 {bn}\{b_n\} 的答案。

    设【结论】对 {bn−1}\{b_{n-1}\} 成立,且存在 aa 为它的符合条件的排列,则对于 {bn}\{b_n\}:

    • 若 bn=1b_n=1,则显然只有在 aa 末尾加上 nn 符合要求,即 f(b,n)=f(b,n−1)f(b,n)=f(b,n-1)。
    • 若 bn=0b_n=0,考虑对于 aa,以下变换方法是唯一的:将 i∼n−1i\sim n-1 都加上 11,然后在末尾加上 ii。
      这样的 ii 共有 n−1n-1 种,即 f(b,n)=f(b,n−1)⋅(n−1)f(b,n)=f(b,n-1)\cdot(n-1)。

    容易发现【结论】对 {x,0},{x,1}\{x,0\},\{x,1\} 成立(其中 x∈{0,1}x\in\{0,1\} 且对结果没有影响),数学归纳可得,【结论】对任意 bb 成立。

    时间复杂度为 O(n)O(n)。

    期望得分 100 分。

    • 1

    信息

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