题解：P11458 [USACO24DEC] All Pairs Similarity P

· · 题解

来个逆天做法。先报复杂度：\mathcal O(n2^{\frac{k}{2}})。

考虑将所有二进制位分成两半，下面我们称他们为高位和低位。设查询的是 x，另一个数是 y。我们的主要思路是：

预处理的方法很简单：首先高位确定后，只有高位的 or / and 的 popcount 有用了，因此只需要算 f_{y_0}(x_1,a,b) 表示高位 y_0 的前提下，低位 x_1，高位的 or / and 的 popcount 分别为 a,b 时的答案之和。进一步观察到最后只是做了 \frac{a}{b}\to \frac{a+c}{b+d} 这样一件事情，那么 c 可以在贡献中乘掉，记录 d 一维就行了。

也就是说，现在要预处理出高位 y_0 的 y 与所有 x_1 的 (c,d) 元组。这个直接暴力做就行了，把非零位置拿出来两两计算，复杂度是 \mathcal O(n2^{\frac{k}{2}}) 的。然后要把所有贡献合并起来，方便后面 \mathcal O(1) 查询。这个容易做，且不是复杂度瓶颈。最后查询直接调用 f 就行了。

总复杂度 \mathcal O(n2^{\frac{k}{2}})。

有个问题是直接做空间好像也是这个复杂度的。不过我们求的信息具有可加性，因此可以像数据结构题中的分块技巧一样，逐块处理，这样空间就是线性的了。

稍微狠狠卡卡常就能过啦。代码仅供参考，如果你写了这个做法，说明你已经和我差不多笨了。

不是最劣解，胜利！

#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=5e5+9,Mod=1e9+7;
int n,K,a[N],inv[25],b[N],tmp[N],tot,rs[(1<<20)+5],pos[N],len;
ll ans[(1<<20)+5];
int bin[(1<<20)+5],tcnt[(1<<11)+5];
int cnt[(1<<10)+2][12][2];
ll pre[(1<<10)+2][12][2],contri[(1<<10)+2][12][12];
ll pw(ll x,ll p){
    ll res=1;
    while(p){
        if(p&1)res=res*x%Mod;
        x=x*x%Mod,p>>=1;
    }
    return res;
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),K=read();
    rep(i,1,n)a[i]=read(),bin[a[i]]++;
    rep(i,1,(1<<K)-1){
        if(bin[i])b[++tot]=i;
    }
    rep(i,1,K)inv[i]=pw(i,Mod-2);
    ll top=min(10,K),top2=K-top;
    rep(i,0,(1<<top)-1){
        memset(cnt,0,sizeof(cnt));
        memset(pre,0,sizeof(pre));
        len=0;
        rep(j,0,(1<<top2)-1){
            tcnt[j]=bin[(i<<top2)|j];
            if(tcnt[j])pos[++len]=j;
        }
        rep(j,0,(1<<top2)-1){
            rep(k,1,len){
                int tpc=__builtin_popcount(j|pos[k]),tc=tcnt[pos[k]];
                cnt[j][tpc][0]+=tc;
                cnt[j][tpc][1]+=tc*__builtin_popcount(j&pos[k]);
            }
        }
        rep(j,0,(1<<top2)-1){
            rep(hig1,0,top){
                rep(k,0,top2){
                    pre[j][hig1][0]+=1ll*cnt[j][k][0]*inv[hig1+k];
                    pre[j][hig1][1]+=1ll*cnt[j][k][1]*inv[hig1+k];
                }
                rep(hig0,0,hig1)contri[j][hig1][hig0]=pre[j][hig1][0]*hig0+pre[j][hig1][1];
            }
        }
        rep(j,1,tot){
            int hig0=__builtin_popcount((b[j]>>top2)&i);
            int hig1=__builtin_popcount((b[j]>>top2)|i);
            int low=b[j]&((1<<top2)-1);
            ll &res=ans[j];
            res+=contri[low][hig1][hig0];
        }
    }
    rep(i,1,tot)rs[b[i]]=ans[i]%Mod;
    rep(i,1,n)write(rs[a[i]]),putchar('\n');
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}