Description：

有 $n$ 组，每组六个数，输出有几对组恰好有 $k$ 个值相同。

$1\le n \le 10^5,0\le k\le 6$

Solution：

我一开始的思路是，先 $2^6=64$ 枚举所有情况，然后用 $hash$ 求出这些位相同的对数，只要把 $hash$ 值存到一个 $hash$ 表里统计即可，然后利用容斥原理：恰好有 $k$ 个值相同的对数 $=$ 大于等于 $k$ 个值相同的对数 $-$ 大于等于 $k+1$ 个值相同的对数 $+$ 大于等于 $k+2$ 个值相同的对数 $\cdots$ ，这样直接统计当前枚举的情况中有几个一，就把对应计数器加一然后最后容斥。

然而这题并没有这么简单，这题的容斥系数并不是简单的 $\pm1$ ，因为对于这样一组数据（来自popoqqq）：

2 3

1 2 3 4 5 5

1 2 3 4 6 6

答案是 $0$ ，但是 $1$ 和 $2$ 这一对被计算了 $C_4^3$ 次，被减掉了 $C_4^4$ 次，也就是说一个 $k+x$ 情况其实可以容斥掉很多 $k$ 的情况，具体来说，是 $C_{k+x}^k$ 个，于是按这个系数容斥即可。

$hash$ 我用的三底数 $+$ 自然溢出。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 100001

typedef unsigned long long ll;

ll a[MAXN][7];

ll C[7][7];

ll S[7];

const ll MOD = 19260817ull;

const ll BASE1 = 99997ull;

const ll BASE2 = 1001001ull;

const ll BASE3 = 1000003ull;

int head[MOD],nxt[MAXN];

ll state1[MAXN],state2[MAXN],state3[MAXN],cnt[MAXN];

int num;

inline void add(ll k1,ll k2,ll k3)

{

	register int hash = k1 % MOD;

	for(register int i = head[hash];i != 0;i = nxt[i])

		if(state1[i] == k1 && state2[i] == k2 && state3[i] == k3){++cnt[i];return;}

	++num;state1[num] = k1;state2[num] = k2;state3[num] = k3;cnt[num] = 1;nxt[num] = head[hash];head[hash] = num;

	return;

}

inline ll query(ll k1,ll k2,ll k3)

{

	register int hash = k1 % MOD;

	for(register int i = head[hash];i != 0;i = nxt[i])

		if(state1[i] == k1 && state2[i] == k2 && state3[i] == k3)return cnt[i];

	return 0;

}

inline int bitcnt(int b)

{

	register int res = 0;

	while(b > 0)

	{

		if(b & 1)++res;

		b = b >> 1;

	}

	return res;

}

ll hashres[MAXN][4];

int main()

{

	scanf("%d%d",&n,&k);

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

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

			cin >> a[i][j];

	C[0][0] = 1;

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

	{

		C[i][0] = 1;

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

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

	}

	register int tot = (1 << 6) - 1;

	memset(S,0,sizeof(S));

	for(register int b = 0;b <= tot;++b)

	{

		num = 0;

		register int cnt = bitcnt(b);

		register ll sum = 0;

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

		{

			hashres[i][1] = hashres[i][2] = hashres[i][3] = 0;

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

			{

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

				{

					hashres[i][1] = hashres[i][1] * BASE1 + a[i][j];

					hashres[i][2] = hashres[i][2] * BASE2 + a[i][j];

					hashres[i][3] = hashres[i][3] * BASE3 + a[i][j];

				}

			}

			sum += query(hashres[i][1],hashres[i][2],hashres[i][3]);

			add(hashres[i][1],hashres[i][2],hashres[i][3]);

		}

		S[cnt] += sum;

		for(register int i = 1;i <= n;++i)head[hashres[i][1] % MOD] = 0; 

	}

	ll ans = 0;

	for(register ll i = k,tag = 1;i <= 6;++i,tag = -tag)ans = ans + S[i] * tag * C[i][k];

	printf("%lld\n",ans);

	return 0;

}