1 条题解

  • 2
    @ 2021-8-1 17:28:01

    观察到所有互不相同的歌曲对答案的贡献独立,于是我们逐歌曲类型考虑。
    假设当前类型出现位置为 a1,a2,,aka_1,a_2,\dots,a_k。我们计算有多少个 P1,P2,S1,S2P_1,P_2,S_1,S_2 使得 (P1,S1)(P_1,S_1) 包含至少一个 aa,和有多少个使得 (P2,S2)(P_2,S_2) 包含至少一个 aa


    对于 (P1,S1)(P_1,S_1)

    定义 c(X,Y)c(X,Y) 为对所有左端点在 {X+1,X+2,,0}\{-X+1,-X+2,\dots,0\},右端点在 {0,1,,Y1}\{0,1,\dots,Y-1\} 的区间的子区间数量和。则:

    $$c(X,Y)=\sum_{i=1}^X\sum_{j=1}^Y\binom{i+j}{2}=\sum_{i=1}^X\sum_{j=1}^Yij+\binom i2+\binom j2 $$$$=(\sum_{i=1}^Xi)(\sum_{j=1}^Yj)+Y(\sum_{i=1}^X\binom{i}{2})+X(\sum_{j=1}^Y\binom{j}{2}) $$

    将这些和预处理即可。

    枚举 P1P_1 里的第一个 aia_i,固定为 aia_i,则有 c(aiai1,nai+1)c(a_i-a_i-1,n-a_i+1)(P1,P2)(P_1,P_2) 满足 P1P_1 包含 aia_i
    最后,如果这个歌曲编号是 xx,将累计起来的贡献乘 c(x,nx+1)c(x,n-x+1) 即可得到总共 (P1,S1,P2,S2)(P_1,S_1,P_2,S_2) 方案数。


    对于 (P2,S2)(P_2,S_2)

    现在我们根本不可能用 c(X,Y)c(X,Y) 了,因为可行的 (P1,P2)(P_1,P_2) 数量依赖于位置。
    定义 d(X,i)d(X,i)(P1,P2)(P_1,P_2) 数量,使得 P2P_2 包含 ii 并且 P2P_2 左端点大于等于 XX。第一发现 P1P_1P2P_2 右端点不受任何限制也和左端点独立,枚举 iiP1P_1 右端点之间的可能左端点数量得到 (P1,P2)(P_1,P_2) 可行右端点数量为

    r=1ni+1r\sum_{r=1}^{n-i+1}r

    通项即可。我们再枚举 P2P_2 左端点的位置,P1P_1 必须在 P2P_2 左端点左边,于是左端点数量为

    r=Xir\sum_{r=X}^ir

    通项即可。按照第一部分一样方法处理。


    所有类型贡献加起来得到答案,时间复杂度 O(n)O(n)

    • 1

    信息

    ID
    163
    时间
    2000ms
    内存
    256MiB
    难度
    9
    标签
    (无)
    递交数
    29
    已通过
    3
    上传者