自动搬运

查看原文

来自洛谷，原作者为

	D2T1 没复活就是似了 | 头发绿绿戴个帽帽，脑袋大大，喜欢唱唱

搬运于2025-08-24 22:31:34，当前版本为作者最后更新于2021-06-11 23:12:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\color{blue}{\text {pwp }~{\to\textbf{My blog}\gets}}~\text{qwq}$

题解

首先考虑一个数不在乎它的每一个数位是什么、哪几个数位相同，只用关心这个数中是否出现了 $0\sim9$ 中的数，所以我们可以用一个 $10$ 位二进制数表示一个输入的数，这个二进制数的第 $k$ 位为 $1$ 表示输入的数中含有数字 $k$。

然后使用一个数组 $k$ 存储每个二进制数的数量。

然后答案就分为两种情况：

• 两个二进制数不同但进行与运算不为零，$O(1024^2)$ 查找整个数组 $k$ 即可。

• 两个二进制数相同，$O(1024)$ 遍历即可。

总复杂度 $O(1024^2)$

代码

//P7617
#include <cstdio>
long long ans;
int k[1024+10],n;

int main(){
	scanf("%d",&n);
	while(n--){
		long long a; int x=0;
		scanf("%lld",&a);
		while(a) x|=(1<<(a%10)),a/=10;
		++k[x];
	}
	for(int i=0; i<1024; ++i)
		for(int j=i+1; j<1024; ++j)
			if(i&j) ans+=(long long)k[i]*k[j];//情况一，乘法原理
	for(int i=0; i<1024; ++i)
		ans+=(long long)k[i]*(k[i]-1)/2;//情况二，组合
	return printf("%lld\n",ans)&0;
}