《小Hi和小Ho的礼物》题目分析

本题是一道容斥原理计数+HASH的题目。

首先我们可以预处理出两个哈希表f和g。

其中f[x]表示 满足Ai + Aj == x且i < j的二元组(i, j)的数量。

g[x]表示 A数组中x的数量。

f和g都可以通过枚举得到，时间复杂度分别是O(N^2)和O(N)。

然后我们可以枚举i和j，即小Hi得到的2袋金币是Ai + Aj。枚举的复杂度是O(N^2)。

这时小Ho的2袋的选择只能从 f[Ai + Aj] 个二元组中选择。考虑到小Ho不能选择Ai也不能选择Aj，根据容斥原理：

如果Ai == Aj 则小Ho总共有 f[Ai + Aj] - 2 * g[Ai] + 3 种选择。

如果Ai != Aj 则小Ho总共有 f[Ai + Aj] - g[Ai] - g[Aj] + 1 种选择。

所以对于每一种小Hi的组合(i, j)，我们都可以利用f和g做到O(1)求出对应的小Ho的选择数量。

于是总的复杂度是O(N^2)。