1711. 大餐计数

考点

• 状态压缩
• 排列组合

题解

class Solution {
	public:
		int countPairs(vector<int>& deliciousnesses) {
			unordered_map<int, long> m;
			long ans = 0, mod = 1e9 + 7;
			for (auto &deliciousness : deliciousnesses) m[deliciousness]++;
			for (auto &[a, v] : m) {
				for (int sum = 1; sum < ( 1 << 22); sum = sum << 1) {
					int b = sum - a;
					if (m.count(b)) {
						ans += a == b ? v * (v - 1) : v * m[b];
					}
				}
			}
			return (int)((ans >> 1) % mod);
		}
};

时间复杂度：\(O\left( n\cdot \log C \right)\)，其中\(C\)为\(2^{21}\)

空间复杂度：\(O\left( n \right)\)

思路

若按传统暴力方法，最高的时间复杂度高达10¹⁰，是绝对不可取的

创建哈希表m记录美味程度相同的下标个数，将所有的下标分类成数个集合；运用集合运算可在常数时间内完成下标两两比较操作

假设当前m的值为{1 : 3, 3 : 3, 7 : 1}，意味着美味程度等于1、3、7的下标个数分别为3、3、1

接下来寻找m中满足两个键的和等于2的幂这一条件的情况个数，常规情况下双重暴力循环，时间复杂度高达平方，也不可取

由于美味程度不超过2²⁰，那么两个键的和也不会超过2²¹

令sum变量为2的幂，从1开始，即2⁰，每次翻倍，直到2²¹终止；循环过程中，用sum减去当前的键，判断m是否存在差值的记录

若存在差值，这里有两种情况：

• 差值等于当前键，那么根据集合运算规则，该条件下的答案为： \[ \frac{\left( \text{键}-1+1 \right) \cdot \left( \text{键}-1 \right)}{2}=\frac{\text{键}\cdot \left( \text{键}-1 \right)}{2} \] 假设当前sum为2，当前键为上述m中的1，有3个下标不同但美味程度均为1的元素

  令这三个下标分别为{0,1,2}，显然该集合两两元素生成不重复的子集只有{0,1}、{0,2}和{1,2}三个

  则答案满足等差数列求和公式： \[ \frac{\left( \text{首项}+\text{末项} \right) \cdot \text{项数}}{2} \]

• 差值等于另一个键，那么根据集合运算规则，该条件下的答案为： \[ \text{当前键映射的值}\cdot \text{差值键映射的值} \] 假设当前sum为4，当前键为上述m中的1，三个下标分别为{0,1,2}；差值键为上述m中的3，三个下标分别为{3,4,5}

  那么{0,1,2}与{3,4,5}两集合中的元素，两两生成不重复的子集的个数为3 * 3 = 9，分别为：

  {0,3}、{0,4}、{0,5}、{1,3}、{1,4}、{1,5}、{2,3}、{2,4}和{2,5}

这里有一个小细节，上述的第二种情况差值等于另一个键在实际过程中会被计算两次

sum为4时，当前键为1，差值键可为3；同样的sum，当前键为3时，差值键也可为1

故而在下方代码中，(v * (v - 1))/2乘了2：

ans += a == b ? v * (v - 1) : v * m[b];

这样可以留到结尾一起除2处理：

return (int)((ans >> 1) % mod);