#2012. [Ceoi2010]Pin

题目描述

输入格式

第1行： N，D

以下N行每行一个字符串

输出格式

一个数：有多少对有且仅有处不相同的字符串。

样例

输入

输出

题解：

n的数据范围为50000，暴力\(O(N^2*D)\)铁T。

先转化一下问题，它问有且仅有d处不同的对数，那我们就将其转化为有且仅有4-d处相同的对数。这两个问题是完全等价的。我们考虑继续简化问题，上面这个问题难在“有且仅有”，发现可以把它转化为“有4-d处相同的对数”，然后利用容斥解决问题。

于是问题就变的很水了，由于只字符串长度固定为4，我们用二进制x表示当前考虑的是哪几位(比如\((1001)_2表示只考虑字符串的第1和第4位\))，先预处理出二进制表示的数\(x∈[0,15]\)所含的1的个数\(sz1[x]\)。

接下来枚举当前数x，然后再枚举n个字符串，根据要考虑的位进行哈希(map搞一下)，然后进行计数，将考虑x这几位的贡献加入\(rc[sz1[x]]\)(\(rc[i]表示有i出相同的字符串的对数\))，最后根据组合数容斥一下，得出答案。

代码如下，详见注释↘

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

char s[50000][5];

int sz1[20],rc[5],n,d;

map<ll,int>mp;

int main(){

	scanf("%d%d",&n,&d);

	for(int i=1;i<=n;i++)scanf("%s",s[i]);

	for(int i=0;i<(1<<4);i++)sz1[i]=sz1[i>>1]+(i&1);//预处理含1个数

	for(int i=0;i<=15;i++){

		ll cnt=0;mp.clear();

		for(int j=1;j<=n;j++){

			ll id=0;//哈希，由于可能出现的可见字符貌似(255???)个左右，下面乘*260

			for(int k=0;k<4;k++)if(i&(1<<k))id=id*260+s[j][k];

			cnt+=mp[id],mp[id]++;

		}

		rc[sz1[i]]+=cnt;

	}

    //根据组合数容斥

	rc[3]-=rc[4]*4;//c(4,3)

	rc[2]-=rc[4]*6+rc[3]*3;//c(4,2),c(3,2)

	rc[1]-=rc[4]*4+rc[3]*3+rc[2]*2;

	rc[0]-=rc[4]+rc[3]+rc[2]+rc[1];

	printf("%d",rc[4-d]);

}