[SDOI2013]泉(容斥)

/*
容斥加上哈希

首先我们可以2 ^ 6枚举相同情况， 然后对于这些确定的位置哈希一下统计方案数
这样我们就统计出了这些不同方案的情况， 然后容斥一下就好了 

*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#define ll unsigned long long 
#define M 101010
#define mmp make_pair
using namespace std;
int read()
{
	int nm = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
	return nm * f;
}
const int mod = 100007, base = 17171;
int n, k, a[M][7], c[7][7], cnt[131];

struct Mp
{
	vector<pair<ll, int> > hs[M];
	void init()
	{
		for(int i = 0; i < mod; i++) vector<pair<ll, int> >().swap(hs[i]);
	}
	
	void insert(ll x)
	{
		int op = x % mod;
		bool f = false;
		for(int i = 0; i < hs[op].size(); i++)
		{
			if(x == hs[op][i].first)
			{
				hs[op][i].second++;
				f = true;
				break;
			}
		}
		if(!f) hs[op].push_back(mmp(x, 1));
	}
	
	ll calc()
	{
		ll ans = 0;
		for(int i = 0; i < mod; i++)
		{
			for(int j = 0; j < hs[i].size(); j++)
			{
				int x = hs[i][j].second;
				ans += 1ll * x * (x - 1) / 2;
			}
		}
		return ans;
	}
}mp;

ll work(int x)
{
	mp.init();
	for(int i = 1; i <= n; i++)
	{
		ll v = 0;
		for(int j = 1; j <= 6; j++)
		{
			v *= base;
			if(x & (1 << (j - 1))) v += a[i][j] + 1;
		}
		mp.insert(v);
	}
	return mp.calc();
}

int main()
{
	n = read(), k = read();
	for(int i = 1; i <= n; i++) for(int j = 1; j <= 6; j++) a[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 - 1] + c[i - 1][j];
	}
	for(int i = 1; i < 64; i++) cnt[i] = cnt[i >> 1] + (i & 1);
	long long ans = 0;
	for(int i = 0; i < 64; i++)
	{
		if(cnt[i] >= k)
		{
			long long t = work(i);
			t = t * c[cnt[i]][k];
			if((cnt[i] - k) & 1) ans -= t;
			else ans += t;
		}
	}
	cout << ans << "
";
	return 0;
}