题目描述

作为光荣的济南泉历史研究小组中的一员,铭铭收集了历史上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 ;
}
05-27 02:05