#P5598. 【XR-4】混乱度

    ID: 4874 远端评测题 1500~5000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>O2优化Lucas 定理洛谷月赛

【XR-4】混乱度

题目描述

小 X 有 nn 种颜色的球,其中第 ii 种颜色的球共有 aia_i 个,同色的球无法区分。定义第 lrl \sim r 种颜色的混乱度 f(l,r)f(l, r) 为:将第 lrl \sim r 种颜色的所有球排成一排,总共的方案数对 pp 取模后的值。小 X 想请你帮忙计算下列式子的值:

l=1nr=lnf(l,r)\sum_{l=1}^n \sum_{r=l}^n f(l, r)

输入格式

第一行两个整数 n,pn, p

第二行 nn 个整数 aia_i

输出格式

一行一个整数,表示答案。

2 2
1 2

3

4 7
1 2 8 9

28

15 5
1 5 26 1 0 5 0 6 7 51 1 5 26 1 0

124

提示

【样例 1 说明】

f(1,1)=1mod2=1f(1,1) = 1 \bmod 2 = 1 f(1,2)=3mod2=1f(1,2) = 3 \bmod 2 = 1 f(2,2)=1mod2=1f(2,2) = 1 \bmod 2 = 1 l=1nr=lnf(l,r)=3\sum_{l=1}^n \sum_{r=l}^n f(l, r) = 3

本题采用捆绑测试。

  • Subtask 1(31 points):1n5×1051 \le n \le 5 \times 10^5aia_i[0,105][0, 10^5] 内均匀随机,时限 1.5 s1.5 \text{ s}
  • Subtask 2(32 points):1n5×1041 \le n \le 5 \times 10^4,时限 5 s5 \text{ s}
  • Subtask 3(37 points):无特殊限制,时限 2.5 s2.5 \text{ s}

对于 100%100\% 的数据,1n5×1051 \le n \le 5 \times 10^50ai10180 \le a_i \le 10^{18}p{2,3,5,7}p \in \{2,3,5,7\}