[51nod1150]Logarithm

Description

给出n个数，求

∑i=1n∑j=1nlog10(AixorAj) xor代表异或运算~ n<=1e5,ai<=1e18

Solution

这种题就是套路了~~ 既然是log10，那么可能的取值就只有18个。 枚举每一个取值x，那么就是异或值在[10^x,10^(x+1)-1)的对数。 枚举每一个数，后面的变成异或值小于等于某个数的对数，然后容斥减掉。 就是经典问题了，放在trie树上跑一跑就好了~ 分类写数位Dp表示不会，求dalao带=w=

Code

#include <cstdio> #include <cstring> #include <algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long ll; const int N=3*1e6+5; int n,tot,trie[N][2],size[N]; ll a[N],mi[61],ans; void insert(ll v) { int x=0; fd(i,60,0) { int t=(v&mi[i])>0; if (!trie[x][t]) trie[x][t]=++tot; x=trie[x][t];size[x]++; } } int calc(ll v,ll val) { int x=0,res=0; fd(i,60,0) { int t0=(v&mi[i])>0,t1=(val&mi[i])>0; if (t1) res+=size[trie[x][t0]]; x=trie[x][t0^t1];if (!x) break; } return res+size[x]; } int main() { scanf("%d",&n);ll l=1,r=9; mi[0]=1;fo(i,1,60) mi[i]=mi[i-1]*2; fo(i,1,n) scanf("%lld",&a[i]),insert(a[i]); fo(j,1,18) { l=r+1;if (l<1e18) r=l*10-1;else r=2*1e18; fo(i,1,n) { ll tmp=calc(a[i],r)-calc(a[i],l-1); ans+=(ll)j*tmp; } } printf("%lld\n",ans); }