LeetCode 1711. 大餐计数（map计数 + 二分查找）

示例 1：
输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。

示例 2：
输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。
 
提示：
1 <= deliciousness.length <= 10^5
0 <= deliciousness[i] <= 2^20

class Solution {
public:
    int countPairs(vector<int>& deliciousness) {
        map<int,long long> m;
        for(auto d : deliciousness)
            m[d]++;//计数
        long long ans = 0, mod = 1e9+7;
        for(int i = 0; i <= 22; i++)
        {	// 枚举 2的幂
            int target = 1 << i;
            for(auto it = m.begin(); it != m.end() && it->first <= target/2; ++it)
            {
                int d1 = target-it->first;//另一份餐的美味程度
                if(m.find(d1) == m.end())//不存在
                    continue;
                if(it->first != d1)//不相等
                    ans = (ans+it->second*m[d1])%mod;
                else//相等 Cn2
                    ans = (ans+m[d1]*(m[d1]-1)/2)%mod;
            }
        }
        return ans;
    }
};