Rivendell’s pearls(pearls.cpp)

【问题描述】

    Rivendell 是一个心灵手巧的男孩子，他在闲暇的时候喜欢做一些小饰品。有一天 Rivendell用漂亮的珍珠做成了 n串手链，并且每串手链都由 4个珍珠构成，并且每粒珍珠都有一种颜色，颜色用小写字母和数字表示。现在他突然想知道这n 串手链中有多少对有且仅有k 粒珍珠是不同颜色的。

【输入格式】

   第一行两个整数 n和 k。接下来 n个长度为 4的字符串。

【输出格式】

     一个整数表示答案。

【样例输入】

    4 2

    0000

    a010

    0202

    a0e2

【样例输出】

    3

【数据规模及约定】

   对于15%的数据，n<=2000

   对于 60%的数据，k<=2。其中50%的数据,k=1

   对于 100%的数据，n<=50000,k<=4

————————————————————————————————

【题解】【字符串哈希+容斥】

#include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;int hash[50010],sum[50010][4];ll ans[5];int n,k;inline int change(char x){	if(x>='0'&&x<='9') return x-'0';	return x-'a'+10;}inline ll cal(int n){	ll sm=0;	int i,x=1;	sort(hash+1,hash+n+1);	for(i=2;i<=n;++i)	 if(hash[i]==hash[i-1]) x++;	  else sm+=(ll)(x-1)*x/2,x=1;	sm+=(ll)(x-1)*x/2;	return sm;}int main(){	freopen("pearls.in","r",stdin);	freopen("pearls.out","w",stdout);	int i,j,l;	scanf("%d%d",&n,&k);	for(i=1;i<=n;++i)	 {	 	char s[5];	 	scanf("%s",s);	 	for(j=0;j<4;++j) sum[i][j]=change(s[j]);	 }	for(i=1;i<=n;++i)	 for(j=0;j<4;++j)	  hash[i]=hash[i]*36+sum[i][j];	ans[0]=cal(n);	for(l=0;l<4;++l)	 {	 	memset(hash,0,sizeof(hash));	 	for(i=1;i<=n;++i)	 	 {	 	 	for(j=0;j