#PQJ1825x9604. QOJ 1825_9604

    ID: 2718 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测枚举

QOJ 1825_9604

标题: Cyberangel - Problem - QOJ.ac

#9604. Cyberangel

Statistics

题目背景

可怜的小 Bronya,因为想不到好的 idea 气的又哭又闹,呜呜呜呜,好可怜啊。

题目描述

Bronya 想给《阿拉哈托·集训队互测》出个新的 DLC,但是想不到好的 idea。

她现在有 n 个 idea,每个 idea 都有一个难度值 ai,满足 1≤ai≤m。

她现在打算在这些 idea 中抽取一个 idea 作为最终 idea,她的抽取方式如下:

随机在 n(n+1)2 个区间中,等概率抽取一个编号区间 [l,r],然后再在 [1,m] 中等概率抽取一个整数作为难度上限 lim,

然后 Bronya 会在所有满足 i∈[l,r],ai≤lim 的 i 中选一个 ai 最大的 i 作为 x。

此时 ax 会作为最终的难度值,若这样的 x 不存在,那最终的难度值为 0。

Bronya 想知道最终难度值的期望,请你帮帮可爱的她。

由于期望是高贵的 10 级算法,小 Bronya 不会,所以请你输出期望乘以 n×(n+1)×m2 的值。

输入格式

第一行两个整数 n,m,分别表示 idea 的数量和难度值的上限。

第二行 n 个整数,第 i 个整数 ai 表示第 i 个 idea 的难度值。

输出格式

一行一个整数 ans,表示最终难度值的期望乘以 n×(n+1)×m2 之后的值。

样例输入

3 4
1 1 4

样例输出

30

样例输入

10 20
5 19 3 14 2 8 18 7 1 5

样例输出

7535

样例解释

考虑最后选出的区间有 [1,1],[1,2],[1,3],[2,2],[2,3],[3,3] 六种可能。

其难度值期望分别是 1,1,74,1,74,1,则最后的答案为 1+1+74+1+74+16×6×4=30

数据范围

对于所有测试点,1≤n≤1×106,1≤m≤1×109。

  • Subtask 1 (5pts): n≤500
  • Subtask 2 (5pts): n≤4000,依赖 Subtask 1。
  • Subtask 3 (5pts): m≤2。
  • Subtask 4 (20pts): m≤50,依赖 Subtask 3。
  • Subtask 5 (10pts): 保证 ai 在 [1,m] 中随机生成,n≤5×105。
  • Subtask 6 (20pts): n≤105,依赖 Subtask 1,2。
  • Subtask 7 (35pts): 无限制,依赖 Subtask 1,2,3,4,5,6。