[容斥]数对

题目描述

两个整数A,B，如果他们某⼀数字相同了，那么(A,B)就是⼀组合法的数对(没有顺序)，现在给定了N个整数，问存在多少对合法的数对呢？

输入

第⼀⾏，⼀个整数N。
接下来N⾏，每⾏⼀个正整数。

输出

输出⼀个整数，表示合法数对个数。

样例输入

3
12
1
2

样例输出

2

提示

对于100%的数据，N≤1000000，每个正整数≤1018。

思路：容斥，加上有一位相同的数对个数，减去有两位相同的数对个数，加上有三位相同的数对个数...

AC代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

ll tot[100005],cnt[100005];

int main()
{
    ll n;scanf("%lld",&n);
    for(ll i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        ll p=0;
        while(x){
            ll t=x%10;
            x/=10;
            p|=(1<<t);
        }
        tot[p]++;//转换为二进制保存出现的数字
    }

    for(ll i=0;i<(1<<10);i++){
        for(ll j=0;j<(1<<10);j++){
            if((j|i)==j) cnt[i]+=tot[j];//cnt[i]表示包含i状态的共有几个数
        }
    }

    ll ans=0;
    for(ll i=1;i<(1<<10);i++){//枚举所有状态，容斥
        if(cnt[i]==0) continue;
        ll num=0;
        ll x=i;
        while(x){
            if(x&1) num++;
            x>>=1;
        }
        if(num&1) ans+=cnt[i]*(cnt[i]-1)/2;
        else ans-=cnt[i]*(cnt[i]-1)/2;
    }
    printf("%lld\n",ans);
    return 0;
}

View Code