题解 | #小红平分糖果#

来点F的笨比纯数学+容斥做法。

记 $S=\sum_i a_i$ ，甲选的两点为A、B，乙选的两点为C、D（A、B不分辨，C、D不分辨）。

先考虑两条线段端点不重合的情况：

先不考虑多边形的限制，只需满足AB与CD有交叉点，这一选法相当于在多边形上取4个点，再将4个点按 ACBD 或 CADB 的顺序排列，总方案数为

N_1 = 2 \binom{S}{4}

从中需要排除掉AB或CD其一在同一条边上的情况，这一选法相当于先取一条边 $a_i$ ，在 $a_i$ 上取3个点，将3个点按 ACB 或 CAD 的顺序排列，再在 $a_i$ 以外的边上取1个点，方案数为

N_2 = 2 \sum_i \binom{a_i}{3} (S-a_i)

还需要排除AB与CD均在同一条边上的情况，这一选法相当于先取一条边 $a_i$ ，在 $a_i$ 上取4个点，再将4个点按 ACBD 或 CABD 的顺序排列，方案数为

N_3 = 2 \sum_i \binom{a_i}{4}

再考虑两条线段有一个端点重合的情况：

先固定两个重合的端点，考虑另外两个端点，这一选法相当于先取一条边 $a_i$ ，在 $a_i$ 上取1个点为A、C，再在 $a_i$ 以外的边上取2个不同点为B、D，方案数为

N_4 = 2 \sum_i a_i \binom{S-a_i}{2}

最终结果即为 $N_1 - N_2 - N_3 + N_4$ 。以下给出Python实现，其他语言可能需要int128或处理逆元。

MOD = 10**9+7
n = int(input())
arr = list(map(int, input().split()))
s = sum(arr) % MOD
ans = s*(s-1)*(s-2)*(s-3)//12
ans -= sum(a*(a-1)*(a-2)//3 * (s-a) % MOD for a in arr)
ans -= sum(a*(a-1)*(a-2)*(a-3)//12 % MOD for a in arr)
ans += sum(a*(s-a)*(s-a-1) % MOD for a in arr)
print(ans % MOD)