自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 21:47:28，当前版本为作者最后更新于2019-07-12 10:40:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

怎么题解都是用哈希的啊，怎么容斥都看不懂啊

我们设f[i]为至少有$i$个泉区的水流指数对应相同

再设g[i]为恰好有$i$个泉区的水流指数对应相同（也就是答案数组）

f[i]可以直接暴力选中$i$个位置，把那些位置上的泉水指数单独拿出来，排个序（懒得写哈希）然后就能直接求了

想想怎么求g[i]

对于$i<j$发现其实g[j]在f[i]里面算了$C(j,i)$遍

那么我们就能得到f[i],g[i]的关系

直接按这个式子dp就行了

数组记得稍微开大点，不然就是91分

复杂度$O(2^6n \log n)=O(n\log n)$

#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>

#define rg register
#define il inline
#define MX (100000 + 500)
#define ll long long

il int read(){
	rg char k = getchar();
	while(k < '0' || k > '9')	k = getchar();
	int x = 0;
	while(k >= '0' && k <= '9'){
		x = x * 10 + k - '0';
		k = getchar();
	}
	return x;
}

ll C(int n ,int m){
	if(n < m)	return 0;
	ll s1 = 1 ,s2 = 1;
	for(rg int i = 0 ; i < m ; ++i)
		s1 *= (ll)n - i ,s2 *= (ll)i + 1;
	return s1 / s2;
}

int tot;
struct data{
	int a[6];
	il bool operator <(const data b)const{
		for(rg int i = 0 ; i < tot ; ++i)
			if(a[i] != b.a[i])	return a[i] < b.a[i];
		return false;
	}
	il bool operator ==(const data b)const{
		for(rg int i = 0 ; i < tot ; ++i)
			if(a[i] != b.a[i])	return false;
		return true;
	}
}org[MX] ,tmp[MX];

ll ans[7];
int use[MX] ,n ,k;
void solve(){
	for(rg int i = 0 ; i < n ; ++i)
		for(rg int j = 0 ; j < tot ; ++j)
			tmp[i].a[j] = org[i].a[use[j]];
	std::sort(tmp ,tmp + n);
	ll _ans = 0 ,tmpsum = 1;
	//tmpsum表示当前有几个连续相同的
	for(rg int i = 1 ; i < n ; ++i){
		if(tmp[i] == tmp[i - 1])	++tmpsum;
		else _ans += tmpsum * (tmpsum - 1) / 2 ,tmpsum = 1;
	}
	_ans += tmpsum * (tmpsum - 1) / 2;
	ans[tot] += _ans;
}
void dfs(int now ,int num){
	if(now == 6){
		if(tot == num)
			solve();
		return ;
	}
	use[tot++] = now;
	dfs(now + 1 ,num);
	--tot;
	dfs(now + 1 ,num);
}

int main(){
	scanf("%d%d" ,&n ,&k);
	for(rg int i = 0 ; i < n ; ++i)
		for(rg int j = 0 ; j < 6 ; ++j)
			org[i].a[j] = read();
			
	for(rg int i = 6 ; i >= k ; --i){
		dfs(0 ,i);
		for(rg int j = i + 1 ; j <= 6 ; ++j){
			ans[i] -= ans[j] * C(j ,i);
		}
	}
	printf("%lld\n" ,ans[k]);
	return 0;
}