Description

Input

Output

Sample Input

Sample Output

HINT

Dragonite修正數(shù)據(jù)

Source

Hash

題解：hash+容斥原理

剛開始hxy手殘了，WA了，然后一臉驚恐的對著ATP說我不會被卡hash 了吧。。。。結(jié)果發(fā)現(xiàn)容斥系數(shù)貌似不太對啊，負號莫名多了。。。。。

將每個字符串hash，然后可以把k個不同，變成6-k個相同。就可以枚舉哪些位置不同，然后消除掉hash中這些位的影響，計算hash值相同的數(shù)的個數(shù)。

我們在計算k的時候?qū)嶋H包含了0..k-1個位置不同的答案，所以需要容斥一下。

容斥的系數(shù)的絕對值就是組合數(shù)，至于正負，必然是一正一負交替排列啦。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#define N 200003#define p 2000001001#define ull unsigned long long #define LL long longusing namespace std;int n,m,ch[N][10],len,q[100];ull mi[N],hp[N],hash1[N];LL ans,base[10][10];void build(){	base[0][0]=1;	base[1][0]=-6; base[1][1]=1;	base[2][0]=15; base[2][1]=-5; base[2][2]=1;	base[3][0]=-20; base[3][1]=10; base[3][2]=-4; base[3][3]=1;	base[4][0]=15; base[4][1]=-10; base[4][2]=6; base[4][3]=-3; base[4][4]=1;	base[5][0]=-6; base[5][1]=5; base[5][2]=-4; base[5][3]=3; base[5][4]=-2; base[5][5]=1;	base[6][0]=1; base[6][1]=-1; base[6][2]=1; base[6][3]=-1; base[6][4]=1; base[6][5]=-1; base[6][6]=1;}void solve(){	for (int i=1;i<=n;i++) {		hash1[i]=hp[i];		for (int j=1;j<=len;j++) hash1[i]-=(ull)mi[q[j]]*ch[i][q[j]];	}	sort(hash1+1,hash1+n+1);	LL sum=1;    for (int i=2;i<=n;i++)     if (hash1[i]==hash1[i-1]) {	   sum++;	   if (i==n) ans+=(LL)base[m][len]*sum*(sum-1)/2;     }     else {     	ans+=(LL)base[m][len]*sum*(sum-1)/2;     	sum=1;	 }}void dfs(int x,int now){	if (x==len+1) {		//for (int i=1;i<=len;i++) cout<<q[i]<<" ";		//cout<<endl; 	//	cout<<ans<<endl;		solve();		return;	}	for (int i=now;i<=6;i++){		q[x]=i;		dfs(x+1,i+1);	}}int main(){	freopen("a.in","r",stdin);	//freopen("my.out","w",stdout);	scanf("%d%d",&n,&m);	mi[0]=1;	for (int i=1;i<=8;i++) mi[i]=mi[i-1]*p;	for (int i=1;i<=n;i++)	 for (int j=1;j<=6;j++) scanf("%d",&ch[i][j]),ch[i][j]++;	for (int i=1;i<=n;i++) 	 for (int j=1;j<=6;j++) hp[i]+=(ull)mi[j]*(ull)ch[i][j];	build(); m=6-m;	for (int i=0;i<=m;i++) {		len=i;		dfs(1,1);	}	printf("%I64d/n",ans);}