小G的LY数对 | 思维、容斥

这里是缅甸北部..

写傻了的D

复杂度:

思路正确，但实现实现的有点傻了

首先考虑 后恰好有两位是1，怎么用数学语言表示：

那么有：

那么很显然，只需要保证，然后求相等即可。

这样就可以先把一边用哈希存起来(被掉了),遍历另一边所有的结果。

这时候得到的结果是包含 的，考虑还满足上述式子：

相等成立的话

必然有：，所以减去相等的方案数就好了。

最后方案数就是答案

这里其实不需要容斥，看rk1代码即可，思路是类似的。

Code:

/*** keep hungry and calm CoolGuang!  ***/
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const ll INF= 1e18+7;
const ll maxn = 1e7+700;
const int M = 1e6+8;
const ll mod= 1e6+7;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a){char c=getchar();T x=0,f=1;while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}a=f*x;}
ll n,m,p;
struct Hash{
    int e,next,w;
}edge[maxn];
int head[maxn];
ll cnt=0;
map<ll,int>ca;
void Insert(int x){
    ll temp=x%mod;
    for(int i=head[temp];~i;i=edge[i].next){
        if(edge[i].e==x){
            edge[i].w++;
            return;
        }
    }
    edge[cnt]=Hash{x,head[temp],1};
    head[temp]=cnt++;
}
ll Find(ll x){
    ll temp=x%mod;
    for(int i=head[temp];~i;i=edge[i].next){
        if(edge[i].e==x) return edge[i].w;
    }
    return 0;
}
ll a[maxn],b[maxn];
int main(){
    memset(head,-1,sizeof(head));
    read(n);read(m);
    for(int i=1;i<=n;i++){
        read(a[i]);
        ca[a[i]]++;
    }
    ll tmp = 0;
    for(int i=1;i<=m;i++){
        read(b[i]);
        tmp += ca[b[i]]*30;
    }
    for(int i=1;i<=n;i++){
        for(int k=0;k<30;k++)
            Insert(a[i]^(1ll<<k));
    }
    ll ans = 0;
    for(int i=1;i<=m;i++)
        for(int k=0;k<30;k++)
            ans += Find(b[i]^(1<<k));
    dl((ans-tmp)/2);
    return 0;
}