本文主要是介绍【校内互测】Rivendell’s pearls（字符串哈希+容斥），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using 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<l;++j) hash[i]=hash[i]*36+sum[i][j];for(j=l+1;j<4;++j) hash[i]=hash[i]*36+sum[i][j];}ans[1]+=cal(n);}ans[1]-=ans[0]*4;if(k==1) {printf("%I64d\n",ans[1]); return 0;}for(l=0;l<4;++l)for(i=l+1;i<4;++i){for(j=1;j<=n;++j) hash[j]=sum[j][l]*36+sum[j][i];ans[2]+=cal(n);}ans[2]-=(ans[0]*4+ans[1]*3);if(k==2) {printf("%I64d\n",ans[2]); return 0;}for(l=0;l<4;++l){for(i=1;i<=n;++i) hash[i]=sum[i][l];ans[3]+=cal(n);}ans[3]-=(ans[2]*2+ans[1]*3+ans[0]*4);if(k==3) {printf("%I64d\n",ans[3]); return 0;}ans[4]=(ll)(n-1)*n/2-ans[3]-ans[2]-ans[1]-ans[0];printf("%I64d\n",ans[4]);return 0;
}这篇关于【校内互测】Rivendell’s pearls（字符串哈希+容斥）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
