3 条题解

  • 0
    @ 2025-11-7 14:32:48

    考虑设状态,设 fi,jf_{i,j} 表示一个 1∼i1\sim i 且有 jj 个逆序对的排列有多少个,转移显然:

    fi,j=∑k=0i−1fi−1,j−kf_{i,j}=\sum_{k=0}^{i-1}f_{i-1,j-k}

    前缀和优化一下做完了,时间复杂度 O(n2)O(n^2)。

    信息

    ID
    575
    时间
    1000ms
    内存
    512MiB
    难度
    10
    标签
    (无)
    递交数
    95
    已通过
    1
    上传者