【校内互测】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; }