[SDOI2013]泉

~~这道题对咱来说算是有buff，咱看到这道题的名字就啪一下点进来了~~

~~泉宝，咱的泉宝，嘿嘿~~(不要在意这个发电的人)

思路

首先仔细读题：有多少对不同的年份恰好有 $K$ 个泉区。这种统计题的基本套路就是容斥(如果你不知道的话，现在就知道啦)，因为刚好 $K$ 个指数相同的年份对(以下简称”元素") 是不好统计的——因为要刚好 $K$ 个元素相同的统计方法应该就是对于每个元素判断其合法性(也许有更优的方法？既然各位Dalao都没提出来咱就当没有啦)，因为是基于枚举方案的统计所以说复杂度为元素数量 $O(n^{2})$，不可接受......

我们转换思路，如果是统计至少 $K$ 个元素相同的话，我们可以先枚举到底必须哪 $K$ 个指数相同(当然，其他指数相同我们是不介意的)，这种情况下我们只需要用桶装下这 $K$ 个指数，对于有相同的这 $K$ 个指数的年份的数量 $Q$ (泉!)，肯定为答案贡献了 $\frac {Q \times (Q-1) }{2}$ (因为一共有这么多对年份对嘛)。从根本上来看，这是统计方式从枚举方案变成了用桶统计同类方案，那么复杂度 $O(n^{2}) \rightarrow O(n)$ (这也是统计题的常见套路啦)

最后的最后，刚好 $K$ 个元素相同和至少 $K$ 个元素相同肯定是不一样的，我们列出两者的关系。为了方便，我们表示前者为 $f(x)$，$g(x)$，那么有：(由基本逻辑得)

$$
g(x) = \sum ^{6} _ {i=x+1}f(i)
$$

这是不是有点像前缀和呢，总之对于 $f(x)$ 我们只需要用 $g(x)$ 减去 $f(y) (y > x)$ 就可以了......个鬼啊！这是咱的第一个思路，是错误的......考虑对于三个指数 $A,B,C$，它对于两个指数 $g(2)$ 的贡献方案有 $(A,B) + C$，$A+(B,C)$，$B+(A,C)$。相当于 $g(x)$ 对 $f(y)$ 的额外非法贡献为 $\binom{x}{y} \times f(x)$。总的来说，我们有：

$$
f(i) = g(i) - \sum ^{6} _{j=i+1} f(j) \times \binom {i} {j}
$$

所以，我们先枚举本回合内只关注哪几个指数，用一个 unordered_map 当作桶，来装下每一个年份的指数哈希值(当然只对关注的指数进行哈希)，由此统计出 $g(x)$，最后用上面的转移式得出 $f(x)$，$f(K)$ 即为答案。

于是我们就A了这道题，可喜可贺可喜可贺，~~完结撒泉宝~~

代码

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define ull unsigned long long
using namespace std;//泉~咱的泉(bushi 
const int MAXN = 1e5 + 6;
const int myBase = 1e9 + 7;
int n,k,w[MAXN][7];
const vector<int> del = {1,2,3,4,5,6};//deleted
const int MAXU = 1e7;
bool vis[MAXU],sel[7];//selected
inline int Execute(){
	unordered_map<ull,int> mp;
	for(int i = 1;i <= n;i++){
		ull hashval = 0;
		for(int j = 1;j <= 6;j++){
			if(sel[j]){
				hashval ^= w[i][j];
			}
			hashval *= myBase;
		}
		mp[hashval]++;
	}
	int ret = 0;
	for(auto i : mp){
		ret += i.second * (i.second-1) / 2;
	}
	return ret;
}
inline int Solve(int k){//枚举关心的指数 
	vector<int> d = del;//因为很懒所以用了next_permutation()和Hash_vis[],大家可以dfs 
	memset(vis,0,sizeof(vis));
	int ans = 0;
	do{
		memset(sel,0,sizeof(sel));
		for(int i = 0;i < k;i++){
			sel[d[i]] = 1;
		}
		int now = 1,val = 0;
		for(int i = 1;i <= 6;i++){
			if(sel[i])val += now;
			now *= 10;
		}
		if(vis[val])continue;
		vis[val] = 1;
		ans += Execute();
	}while(next_permutation(d.begin(),d.end()));
	return ans;
}
int l[7],only[7],C[9][9];
inline void Pre(){//预处理C 
	for(int i = 0;i <= 7;i++)C[i][0] = 1;
	for(int i = 1;i <= 7;i++){
		for(int j = 1;j <= 7;j++){
			C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
	}
	return ;
}
int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	Pre();
	cin>>n>>k;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= 6;j++){
			cin>>w[i][j];
		}
	}
	for(int i = 1;i <= 6;i++){
		l[i] = Solve(i);
	}
	l[0] = n * (n-1) / 2;
	for(int i = 6;i >= 0;i--){
		only[i] = l[i];
		for(int j = i+1;j <= 6;j++){
			only[i] -= only[j] * C[j][i];
		}
	}
	cout<<only[k];
	return 0;
}

因为咱非常懒，用了很多低效率的 STL 和算法，所以时间耗时大。如果手写哈希或者排序之类的效率会高的多