[校内互测]Rivendell’s pearls（hash+容斥原理）

2019-11-06 06:19:31

字体：大中小

来源：转载

供稿：网友

=== ===

这里写图片描述

=== ===

题解

没错这本来应该是ATP胡策第一次A题但是然而but被卡了hash然后就变成了暴力分。。这里贴的这个破代码就是考试的时候写的。。幸亏拼上了暴力不然TMD肯定一分也没有。。最后改了cloverhxy的万能质数就过了。。

hash的思路还是比较显然的，因为位数非常的少，所以可以暴力选择某些位让它们作为不相同的位，然后把这几位在原串里面去掉，搞一坨hash值出来排个序就能知道到底几对数字相等了。一开始觉得这么做就可以了但是发现算的乱七八糟答案多了好多。。这是为什么呢。。

原因就是它选出来的那几位不一定全都是不相等的，因为我们只是“假装”那几位在每一对串里面都不一样然后强行把它抠出来，但是有可能选出来的某些位在某几对串里面是相等的。也就是说题目中要求的是恰好k位不同，而我们算的是至多k位不同，所以说还得减去那些不同的位数比k少的。

然后这就是一个容斥的思路了。考虑有什么东西被多选了，每个被多选了几次。以某一对串里面选定了2个字符让它们相等为例，如果这两个串是“aabc”和“aade”这种东西，也就是恰好有2个字符相等，那么肯定能正确的判定出来；但是如果是“aaab”和“aaac”这种有3个字符相等的东西，那么这三个相等的a我们任意留下两个，都会判定它们相等。也就是说这一对不合法的串被多计算了C23 $C_3^2$ 次。

但是可以发现如果仅仅选出所有3个字符相等的串然后乘上C23 $C_3^2$ 再减去答案还是不对的，这是因为如果这个串有4个字符相等，它们也会被重复计算然后多减去。首先在算2个字符相等的时候它们被多算了C24 $C_4^2$ 次，然后在减去3个字符相等的时候它们每一个被重复计算了C34 $C_4^3$ 次，每一次乘上一个C23 $C_3^2$ 。可以发现它们被多减去了C24 $C_4^2$ 次。要把这些都加回来。剩下的情况以此类推，在dfs的时候控制一下容斥系数就可以了。

代码

请自行忽略奇怪的函数名和强行拼进去的暴力。。。。

#include<cstdio>#include<cstring>#include<algorithm>#define ULL unsigned long longusing namespace std;const ULL Mn=2000001001;int n,k,C[10][10];ULL poww[10],hash[50010],ans,num[50010];char c[50010][6];bool chs[10];int comp(char *p,char *q){ int tot=0; for (int i=0;i<4;i++) if (p[i]!=q[i]) ++tot; return tot;}void qwert(){ int ans=0; for (int i=1;i<n;i++) for (int j=i+1;j<=n;j++) if (comp(c[i],c[j])==k) ++ans; PRintf("%d/n",ans);}ULL calc(){ ULL tot=1,sum=0; for (int i=1;i<=n;i++){ num[i]=hash[i]; for (int j=0;j<4;j++) if (chs[j]==false)//在原hash值的基础上直接相减 num[i]-=c[i][j]*poww[j]; } sort(num+1,num+n+1); for (int i=1;i<=n;i++) if (num[i]==num[i-1]&&i!=1) ++tot; else{sum+=tot*(tot-1)/2;tot=1;}//计算所有相等的对数 sum+=tot*(tot-1)/2; return sum;}void dfs(int i,int pos,int dlt,int limit){ if (i==limit+1){ ans+=dlt*C[limit][k]*calc(); return; } for (int j=pos;j<4;j++) if (chs[j]==false){ chs[j]=true;//枚举哪些位置相等 dfs(i+1,j+1,dlt,limit); chs[j]=false; }}void poiuy(){ int dlt=1; for (int i=0;i<=5;i++) C[i][0]=1; for (int i=1;i<=5;i++) for (int j=0;j<=i;j++)//预处理组合数 C[i][j]=C[i-1][j]+C[i-1][j-1]; poww[0]=Mn; for (int i=1;i<=8;i++) poww[i]=Mn*poww[i-1]; for (int i=1;i<=n;i++) for (int j=0;j<4;j++) hash[i]+=(ULL)c[i][j]*poww[j];//预处理每个串原始的hash值 k=4-k; for (int i=k;i<=4;i++){ memset(chs,false,sizeof(chs)); dfs(1,0,dlt,i); dlt=-dlt; } printf("%I64u/n",ans);}int main(){ freopen("pearls.in","r",stdin); freopen("pearls.out","w",stdout); scanf("%d%d/n",&n,&k); for (int i=1;i<=n;i++) gets(c[i]); if (n<=1500) qwert(); else poiuy(); return 0; }