【[SDOI2013]泉】

\(hash\)+容斥

但是看到这个令人愉快的数据范围还是直接枚举子集吧

首先我们发现\(6\)这个东西简直是小的可怜，复杂度里肯定有\(2^6\)的

于是我们可以直接先枚举子集，把所有状态的对应相等的位置有多少对搞出来

因为一个答案在一个集合里被算过那么就一定在子集里被算过

之后我们倒着枚举子集，顺便容斥就好了

代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<tr1/unordered_map>

#define re register

#define maxn 100005

#define uint unsigned long long

#define pt putchar(1)

#define lowbit(x) ((x)&(-x))

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

using namespace std::tr1;

inline int read()

{

	char c=getchar();

	int x=0;

	while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();

	return x;

}

int a[maxn][7];

int n,m;

int dp[65];

LL ans;

uint base=666233;

inline int cnt(int x) {int tot=0;while(x) tot++,x-=lowbit(x);return tot;}

unordered_map<uint,int> ma;

inline int count(int x)

{

	int tot=0,ct=0;int b[10];

	while(x){ct++;if(x&1) b[++tot]=ct;x>>=1;}

	ma.clear();

	int now=0;

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

	{

		uint k=0;

		for(re int j=1;j<=tot;j++)

			k=k*base+a[i][b[j]];

		now+=ma[k];

		ma[k]++;

	}

	return now;

}

int main()

{

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

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

		for(re int j=1;j<=6;j++) a[i][j]=read();

	int N=(1<<6);N--;

	for(re int i=0;i<=N;i++) dp[i]=count(i);

	for(re int i=N;i;i--)

		for(re int t=i;t;t=(t-1)&i) dp[i^t]-=dp[i];

	for(re int i=0;i<=N;i++)

		if(cnt(i)==m) ans+=dp[i];

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

	return 0;

}