题解：P11458 [USACO24DEC] All Pairs Similarity P

· · 题解

水个 O(2^KK) 的题解。

记 \operatorname {count}(i) 为 i 的二进制表示中 1 的个数，容易发现 \frac{\operatorname {count}(i \And j)}{\operatorname {count}(i|j)}=\frac{\operatorname {count}(i)+\operatorname {count}(j)}{\operatorname {count}(i|j)}-1。

于是我们只用管分母就好了，也就是要对于 a_i 求出：

\sum_{k|a_i=k} \sum_{k|a_j=k} \frac{[a_i|a_j=k]}{\operatorname {count}(k)}

以及

\sum_{k|a_i=k} \sum_{k|a_j=k} \frac{[a_i|a_j=k]\operatorname {count}(a_j)}{\operatorname {count}(k)}

不考虑 [a_i|a_j=k] 的限制，以上两个式子都可以视作做一遍按位或的 FMT，将得到的数组每一位除以 \operatorname {count}(k)，再做一遍按位与的 FMT 得到的结果，但是加上这个限制之后，我们就不能直接除以该值，考虑乘上一个容斥系数，容易发现这个容斥系数只与 \operatorname {count}(k) 有关。设 \operatorname {count}(k) = x 时容斥系数为 f_x。

对于容斥系数要求满足对于任意 y，\sum_{x=y}^{K} C_{K-y}^{K-x}f_x = \frac{1}{y}，移项即可得到递推式 f_K = \frac{1}{K}，f_x=\frac{1}{k}-\sum_{y=x+1}^{K}C_{K-x}^{K-y}f_y，直接递推求即可。

然后就做完了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1<<20,mod = 1e9+7;
int n,K;
int a[N];
ll s1[N],s2[N];
ll V[21],C[21][21],inv[21];
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>K;
    for(int i = 1;i <= n;i++)
    {
        int x;cin>>x;
        a[i] = x;
        s1[x]++;
        s2[x] += __builtin_popcount(x);
    }
    inv[1] = 1;
    for(int i = 2;i <= K;i++) inv[i] = mod - mod/i*inv[mod%i]%mod;
    for(int i = 0;i <= K;i++)
    {
        C[i][0] = 1;
        for(int j = 1;j <= i;j++) C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
    }
    V[K] = inv[K];
    for(int i = K-1;i;i--)
    {
        V[i] = inv[i];
        for(int j = i+1;j <= K;j++) V[i] = (V[i] + mod - V[j]*C[K-i][K-j]%mod)%mod;
    }
    for(int i = 1;i < (1<<K);i<<=1)
        for(int j = 0;j < (1<<K);j += i<<1)
            for(int k = 0;k < i;k++)
            {
                s2[i+j+k] += s2[j+k];
                s1[i+j+k] += s1[j+k];
            }
    for(int i = 1;i < (1<<K);i++)
    {
        s2[i] = s2[i]*V[__builtin_popcount(i)]%mod;
        s1[i] = s1[i]*V[__builtin_popcount(i)]%mod;
    }
    for(int i = 1;i < (1<<K);i<<=1)
        for(int j = 0;j < (1<<K);j += i<<1)
            for(int k = 0;k < i;k++)
            {
                s2[j+k] += s2[i+j+k];
                s1[j+k] += s1[i+j+k];
            }
    for(int i = 1;i <= n;i++)
    {
        cout<<(__builtin_popcount(a[i])*s1[a[i]] + s2[a[i]]-n+mod)%mod<<"\n";
    }
    return 0;
}