专栏文章

题解：P11458 [USACO24DEC] All Pairs Similarity P

llzytag
P11458题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqonswp
此快照首次捕获于
2025/12/04 08:13
3 个月前
此快照最后确认于
2025/12/04 08:13
3 个月前
查看原文
水个 O(2KK)O(2^KK) 的题解。
记 count⁡(i)\operatorname {count}(i) 为 ii 的二进制表示中 11 的个数，容易发现 count⁡(i&j)count⁡(i∣j)=count⁡(i)+count⁡(j)count⁡(i∣j)−1\frac{\operatorname {count}(i \And j)}{\operatorname {count}(i|j)}=\frac{\operatorname {count}(i)+\operatorname {count}(j)}{\operatorname {count}(i|j)}-1。
于是我们只用管分母就好了，也就是要对于 aia_i 求出： ∑k∣ai=k∑k∣aj=k[ai∣aj=k]count⁡(k)\sum_{k|a_i=k} \sum_{k|a_j=k} \frac{[a_i|a_j=k]}{\operatorname {count}(k)} 以及 ∑k∣ai=k∑k∣aj=k[ai∣aj=k]count⁡(aj)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)} 不考虑 [ai∣aj=k][a_i|a_j=k] 的限制，以上两个式子都可以视作做一遍按位或的 FMT，将得到的数组每一位除以 count⁡(k)\operatorname {count}(k)，再做一遍按位与的 FMT 得到的结果，但是加上这个限制之后，我们就不能直接除以该值，考虑乘上一个容斥系数，容易发现这个容斥系数只与 count⁡(k)\operatorname {count}(k) 有关。设 count⁡(k)=x\operatorname {count}(k) = x 时容斥系数为 fxf_x。
对于容斥系数要求满足对于任意 yy，∑x=yKCK−yK−xfx=1y\sum_{x=y}^{K} C_{K-y}^{K-x}f_x = \frac{1}{y}，移项即可得到递推式 fK=1Kf_K = \frac{1}{K}，fx=1k−∑y=x+1KCK−xK−yfyf_x=\frac{1}{k}-\sum_{y=x+1}^{K}C_{K-x}^{K-y}f_y，直接递推求即可。
然后就做完了。
代码：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...