Rivendell’s pearls(pearls) 【问题描述】 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 对于 75%的数据，字符串中只有字母a 到f 对于 100%的数据，n<=50000,k<=4
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ul unsigned long long #define LL long long #define p 2000001001 #define N 50003 using namespace std; int n,m,k,len; char s[10]; int ch[N][10],ans[N],vis[N]; LL tot,base[10][10]; ul mi[N],hash[N]; struct data { int x; ul num,num1; }a[N]; int cmp(data x,data y) { return x.num<y.num||x.num==y.num&&x.num1<y.num1; } void solve1() { for (int i=1;i<=n;i++) { a[i].num=hash[i],a[i].num1=0; a[i].x=i; for (int j=1;j<=k;j++) a[i].num-=ch[i][ans[j]]*mi[ans[j]-1], a[i].num1-=ch[i][ans[j]]*mi[ans[j]-1]; } sort(a+1,a+n+1,cmp); LL sum=1,sum1=1; for (int i=2;i<=n;i++) if (a[i].num==a[i-1].num) { if (a[i].num1==a[i-1].num1) sum1++; else tot-=(sum1-1)*sum1/2,sum1=1; sum++; if (i==n) tot-=sum1*(sum1-1)/2,tot+=(sum-1)*sum/2;//cout<<tot<<endl; } else { tot-=(sum1-1)*sum1/2; tot+=(sum-1)*sum/2; sum=1,sum1=1; } } void dfs(int x,int now) { if (x==k+1) { if (k==1) solve1(); return; } for (int i=now;i<=4;i++) { ans[x]=i; dfs(x+1,i+1); } } void solve() { for (int i=1;i<=n;i++) { a[i].num=hash[i],a[i].num1=0; a[i].x=i; for (int j=1;j<=len;j++) a[i].num-=ch[i][ans[j]]*mi[ans[j]-1]; } sort(a+1,a+n+1,cmp); LL sum=1,ans1=base[k][len]; for (int i=2;i<=n;i++) if (a[i].num==a[i-1].num) { sum++; if (i==n) tot+=ans1*(sum-1)*sum/2; } else { tot+=ans1*(sum-1)*sum/2; sum=1; } } void dfs1(int x,int now) { if (x==len+1) { solve(); return; } for (int i=now;i<=4;i++) { ans[x]=i; dfs1(x+1,i+1); } } LL calc() { sort(hash+1,hash+n+1); LL sum=1,ans1=0; for (int i=2;i<=n;i++) if (hash[i]==hash[i-1]) { sum++; if (i==n) ans1+=sum*(sum-1)/2; } else { ans1+=sum*(sum-1)/2; sum=1; } return ans1; } int main() { freopen("pearls.in","r",stdin); freopen("pearls.out","w",stdout); scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) { scanf("%s",s+1); for (int j=1;j<=4;j++) ch[i][j]=s[j]; } mi[0]=1; for (int i=1;i<=4;i++) mi[i]=mi[i-1]*p; for (int i=1;i<=n;i++) { for (int j=1;j<=4;j++) hash[i]+=mi[j-1]*ch[i][j]; } if (k==0) { sort(hash+1,hash+n+1); LL sum=1,ans1=0; for (int i=2;i<=n;i++) if (hash[i]==hash[i-1]) { sum++; if (i==n) ans1+=sum*(sum-1)/2; } else { ans1+=sum*(sum-1)/2; sum=1; } printf("%I64d\n",ans1); return 0; } if (k==1) { dfs(1,1); printf("%I64d\n",tot); return 0; } base[2][0]=6; base[2][1]=-3; base[2][2]=1; base[3][0]=-4; base[3][1]=3; base[3][2]=-2; base[3][3]=1; base[4][0]=1; base[4][1]=-1; base[4][2]=1; base[4][3]=-1; base[4][4]=1; for (int i=1;i<=k;i++) { len=i; dfs1(1,1); } printf("%I64d\n",tot+calc()*base[k][0]); }
