[SDOI2013]泉
题目描述
作为光荣的济南泉历史研究小组中的一员，铭铭收集了历史上 $x $ 个不同年份时不同泉区的水流指数，这个指数是一个小于. $ 2^{30} $ 的非负整数。第 \(i\) 个年份时六个泉区的泉水流量指数分别为 $ A(i,l)，A(i,2)，A(i,3)，A(i,4)， A(i,5), A(i,6)$。
现在铭铭希望知道有多少对不同的年份：$i $ 和 \(j\) ,满足这两年恰好有K个泉区的泉水流 \(S\) 指数对应相同。
对于 $ 100% $ 的数据, $ 0\leqslant K \leqslant 6 $, 且所有数据中 \(K\) 是等概率出现的, 即对于任意的 $0\leqslant x $ 都有大约 \(\dfrac{1}{7}\) 的数据中 \(K=x\).
$ N<=100000 $
思路点拨
题目种的 恰好 这个条件并不是很好解决，我们考虑使用二项式反演将其转换成 至少 或者 不超过 的问题。我们设 \(f(x)\) 表示恰好有 \(x\) 个泉区水流指数相同的点对数量； \(g(x)\) 表示 至少有 \(x\) 个泉区流水指数相同的点对数量。特别的，\(g(x)\) 的点对计数是可以重复的。例如当 \(x=3\) 的时候，如果存在两个点对 \(i,j\) ，满足有 \(5\) 个泉水流水指数相同，那么这就会被记录 \(C_{5}^{3}\) 次。
根据定义，我们有：
我们简单反演得到：
现在我们只需要考虑 \(g(x)\) 的求解就可以了。一个比较好想的想法就是，我们枚举有哪些位置上的流水指数是相同的，接下来就只需要数一下有那些泉水这些点对的确是相同的就可以了。具体实现的话，以这些被我们选中的位置为关键字排序双指针扫一遍就可以了，这一点相信大家来做这题还是会的。
时空复杂度分析
我们枚举 \(g(x)\) 的时候，一共会枚举到 \(2^6\) ，并且对于每一次枚举之后都需要重新排序，所以时间复杂度就是 \(O(2^6 n \log n)\) ,好在STL的排序比较快，所以可以过。