[SDOI2013]泉

题目描述

作为光荣的济南泉历史研究小组中的一员，铭铭收集了历史上x个不同年份时不同泉区的水流指数，这个指数是一个小于. 2^30的非负整数。第i个年份时六个泉区的泉水流量指数分别为 A(i,l)，A(i，2)，Mi，3)，A(i,4), A(i,5)与 A(i,6)。

现在铭铭希望知道有多少对不同的年份：i和j,满足这两年恰好有K个泉区的泉水流S指数对应相同。

输入输出格式

输入格式：

第一行有2个整数，分别是N和K

之后N行，每行有6个整数。第i行的第j个数字A(i，j)表示第i个年份屮第j个泉区的泉水流量指数。

输出格式：

一个整数表示有多少对不同的年份满足恰有K个区的泉水流量指数对应相同。

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

对于 100%的数据, 0<=K <=6, 且所有数据中K是等概率出现的, 即对于任意的 0<=x都有大约 1/7 的数据中 K=x. N<=100000

题解

这题卡哈希好蛋疼

观察题目发现k很小,所以可以枚举所有情况

用哈希表存储每种哈希值出现的次数

然后因为是恰好k个泉区

所以我们要容斥掉所有的>k个泉区的方案数

答案就是至少k个泉区的方案数 - 至少是k+1个泉区的方案数 * \(C(k + 1 , k)\) + 至少是k+2个泉区的方案数 * \(C(k+2,k)\)

为什么要去乘组合数呢?

因为每个至少是\(k+a(a>0)\)个泉区相同的方案对至少是k个泉区相同的方案数的贡献是\(C(k+a,k)\)

而我们要求的是恰好,所以要将他们减去

代码

#include<cstdio>

#include<cstring>

#include<cstring>

#include<iostream>

#include<algorithm>

# define LL long long

# define ull unsigned long long

const ull Base = 233333 ;

const ull mod = 999983 ;

const int M = 100005 ;

using namespace std ;

inline int read() {

	char c = getchar() ; int x = 0 , w = 1 ;

	while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }

	while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }

	return x*w ;

}

int n , m ;

int val[M][8] ;

int c[8][8] ;

LL Ans ;

int hea[M * 10] , num ;

struct E {

	int Nxt , cnt ; ull to ;

} edge[M * 10] ;

inline int chk(int x) {

	int ret = 0 ;

	for(int i = 1 ; i <= 6 ; i ++)

	    if(x & (1 << (i - 1)))

		    ++ret ;

	return ret ;

}

inline void insert(ull x) {

	int u = x % mod ;

	for(int i = hea[u] ; i ; i = edge[i].Nxt) {

		ull v = edge[i].to ;

		if(v == x) { edge[i].cnt ++ ; return ; }

	}

	edge[++num].Nxt = hea[u] ; edge[num].to = x ; edge[num].cnt = 1 ; hea[u] = num ;

}

inline void Solve(int x) {

	int ret = 0 ;

	LL temp = 0 ;

	for(int i = 1 ; i <= n ; i ++) {

		ull h = 0 ;

		for(int j = 1 ; j <= 6 ; j ++)

		    if(x & (1 << (j - 1)))

		        h = h * Base + val[i][j] ;

	    insert(h) ;

	}

	for(int i = 1 ; i <= 6 ; i ++) if(x & (1 << (i - 1))) ++ret ;

	for(int i = 1 ; i <= num ; i ++) temp += 1LL * ((edge[i].cnt - 1) * edge[i].cnt) / 2 ;

	temp *= c[ret][m] ;

	memset(hea , 0 , sizeof(hea)) ; num = 0 ;

	if((ret - m) % 2) Ans -= temp ;

	else Ans += temp ;

}

int main() {

	n = read() ; m = read() ;

	for(int i = 1 ; i <= n ; i ++)

	    for(int j = 1 ; j <= 6 ; j ++)

	        val[i][j] = read() ;

	c[0][0] = 1 ;

	for(int i = 1 ; i <= 6 ; i ++) {

	    c[i][0] = 1 ;

		for(int j = 1 ; j <= i ; j ++)

	        c[i][j] = c[i - 1][j] + c[i - 1][j - 1] ;

	}

	for(int i = 0 ; i < (1 << 6) ; i ++)

	    if(chk(i) >= m)

	        Solve(i) ;

	cout << Ans << endl ;

	return 0 ;

}