[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 << "\n";

	return 0;

}