首页 > 其他分享 >集合/二进制运算合集

集合/二进制运算合集

时间:2024-11-04 08:59:41浏览次数:3  
标签:frac 运算 二进制 sum IFWT varnothing FWT 卷积 合集

RT,主要内容涉及有 高维前缀和(子集DP),高维后缀和,高维差分,快速沃尔什变换,子集卷积。

参考资料:

知识点合集

高维前缀和

用于求解 \(f(S)=\sum_{T\subseteq S}g(T)\)。

    for(int i=0;i<(1<<n);i++)f[i]=g[i];
    for(int j=0;j<n;j++){
        for(int i=0;i<(1<<n);i++)if((i>>j)&1)f[i]+=f[i^(1<<j)];
    }

本质原理:DP。统计依次前 \(j\) 物品出现的时候的贡献。

高维差分

考虑子集反演 \(f(S)=\sum_{T\subseteq S}g(T)\implies g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)\)

根据这个,其实可以考虑 FWT 进行计算,不过过于累赘。

我们发现这玩意在高维前缀和把加号换成减号容斥系数正好正确。

    for(int i=0;i<(1<<n);i++)g[i]=f[i];
    for(int j=0;j<n;j++){
        for(int i=0;i<(1<<n);i++)if((i>>j)&1)g[i]-=g[i^(1<<j)];
    }

快速沃尔什变换

应用于计算二进制卷积。

\(or\) 卷积

计算 \(C_i=\sum_{(j|k)=i}A_jB_k\)

我们定义 \(FWT(A)_i=\sum_{j|i=i}A_j\)

则有:

\[\begin{aligned} (FWT(A)·FWT(B))_i&=\sum_{j|i=i,k|i=k}A_jB_k\\ &=\sum_{(j|k)|i=i}A_jB_k\\ &=FWT(C)_i \end{aligned} \]

所以我们只需要考虑 \(FWT,IFWT\) 怎么求。

考虑钦定长度为 \(2^n\),使用分治进行计算。

定义将 \(A\) 的前 \(2^{n-1}\) 以及后 \(2^{n-1}\) 位划分为序列 \(A_0,A_1\)。

不难发现 \(FWT(A)=merge(FWT(A_0),FWT(A_0)+FWT(A_1))\)

而 \(IFWT\) 是逆运算,不难得到:\(IFWT(A)=merge(IFWT(A_0),IFWT(A_1)-IFWT(A_0))\)

(事实上,从FMT的视角来看,这玩意是高维前缀和)

\(and\) 卷积

类比 or,设计 \(FWT(A)_i=\sum_{(j\&i)=i}A_j\),也容易得到 \(FWT(C)=FWT(A)·FWT(B)\)。

而根据分治法的结果,同样有:

\(FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0))\)

(高维后缀和)

\(IFWT(A)=merge(IFWT(A_0)-IFWT(A_1),IFWT(A_1))\)

\(xor\) 卷积

这个比较抽象,设 \(d(i)=popcount(i)\bmod 2\)。

设 \(FWT(A)_i=\sum_{j}(-1)^{d(j\&i)}A_j\)

根据 \((j\&i)\oplus (k\&i)=(j\oplus k)\&i\)。

同样有:

\[\begin{aligned} [FWT(A)·FWT(B)]_i&=\sum_{j}\sum_{k}(-1)^{d(k\&i)}B_k(-1)^{d(j\&i)}A_j\\ &=\sum_{j,k}(-1)^{d(k\&i )+d(j\& i)}A_jB_k\\ &=\sum_{j,k}(-1)^{d(k\&i )\oplus d(j\& i)}A_jB_k\\ &=\sum_{j,k}(-1)^{d((j\oplus k)\&i)}A_jB_k\\ &=FWT(C)_i \end{aligned} \]

考虑计算 \(FWT(A)\)。

容易发现 \(A_0,A_1\) 拼起来后,\(A_1\) 的值作用于后半部分会导致最高位多出一个 \(1\)。

所以有 \(FWT(A)=merge(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))\)

因此有 \(IFWT(A)=merge(\frac{IFWT(A_0)+IFWT(A_1)}{2},\frac{IFWT(A_0)-IFWT(A_1)}{2})\)

写法:考虑类比FFT,迭代换递归,但由于位置始终不变,所以不需要蝴蝶变换。

#include<bits/stdc++.h>
using namespace std;
#define N (1<<17)+5
const int p=998244353;
int n;
void ad(int &x,int y){
    x+=y;if(x>p)x-=p;if(x<0)x+=p;
}
void fwtor(int a[],int d,int tag){
    for(int len=1;len<(1<<d);len<<=1){
        for(int j=0;j<(1<<d);j+=(len<<1)){
            for(int k=0;k<len;++k)ad(a[j+k+len],a[j+k]*tag);
        }
    }
}
void fwtand(int a[],int d,int tag){
    for(int len=1;len<(1<<d);len<<=1){
        for(int j=0;j<(1<<d);j+=(len<<1)){
            for(int k=0;k<len;++k)ad(a[j+k],a[j+k+len]*tag);
        }
    }
}
void fwtxor(int a[],int d,int tag){
    for(int len=1;len<(1<<d);len<<=1){
        for(int j=0;j<(1<<d);j+=(len<<1)){
            for(int k=0;k<len;++k){
                int x=a[j+k],y=a[j+k+len];
                a[j+k]=1ll*(x+y)%p*tag%p;
                a[j+k+len]=1ll*(p+x-y)%p*tag%p;   
            }
        }
    }
}
int a[N],b[N],c[N],tmpa[N],tmpb[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;for(int i=0;i<(1<<n);++i)cin>>a[i];
    for(int i=0;i<(1<<n);i++)cin>>b[i];
    memcpy(tmpa,a,sizeof a);memcpy(tmpb,b,sizeof b);
    fwtor(a,n,1);fwtor(b,n,1);
    for(int i=0;i<(1<<n);i++)c[i]=1ll*a[i]*b[i]%p;
    fwtor(c,n,-1);
    for(int i=0;i<(1<<n);i++)cout<<c[i]<<" ";cout<<"\n";
    memcpy(a,tmpa,sizeof a);memcpy(b,tmpb,sizeof b);
    fwtand(a,n,1);fwtand(b,n,1);
    for(int i=0;i<(1<<n);i++)c[i]=1ll*a[i]*b[i]%p;
    fwtand(c,n,-1);
    for(int i=0;i<(1<<n);i++)cout<<c[i]<<" ";cout<<"\n";
    memcpy(a,tmpa,sizeof a);memcpy(b,tmpb,sizeof b);
    fwtxor(a,n,1);fwtxor(b,n,1);
    for(int i=0;i<(1<<n);i++)c[i]=1ll*a[i]*b[i]%p;
    fwtxor(c,n,(p+1)>>1);
    for(int i=0;i<(1<<n);i++)cout<<c[i]<<" ";cout<<"\n";
}

注意到 IFWT Xor 我们可以最后再除掉 \(2^d\) 也是可以的

注意到三个卷积的形式其实是一样的,也就是说我们会有:

  1. \(FWT(\sum k_iF_i(x))=\sum k_iFWT(F_i(x))\)

  2. \(\prod F_i(x)=IFWT(\prod FWT(F_i(x)))\)

    前面的乘法是做异或卷积,后面是对位相乘

子集卷积

求 \(C_S=\sum_{T\subseteq S}A_TB_{S-T}\)。

考虑到这等价于:

\(C_i=\sum_{j\&k =0,j|k=i}A_jB_k\)。

而 \(j\&k=0\) 可以描述为 \(popcount(j)+popcount(k)+popcount(j\&k)=popcount(j|k)\)。

这里考虑 \(or\) 卷积的 FWT。

所以设 \(FWT(A,I)_i=\sum_{j|i,popcount(j)=I}A_j\)。

则有 \(FWT(C,I)=\sum_{J}FWT(A,J)FWT(B,I-J)\)。

然后 \(IFWT\) 回去得到 \(C_I\),则 \(C_S=C_{|S|}[S]\)。

\(O(n^22^n)\)。

#include<bits/stdc++.h>
using namespace std;
int a[20][1<<20],b[20][1<<20],c[20][1<<20];
#define bit __builtin_popcount
const int p=1e9+9;
void ad(int &x,int y){
    x+=y;if(x>p)x-=p;
    if(x<0)x+=p;
}
void fwtor(int a[],int n,int tag){
    for(int len=1;len<(1<<n);len<<=1)for(int j=0;j<(1<<n);j+=len<<1)for(int k=0;k<len;k++)ad(a[j+k+len],a[j+k]*tag);
}
int read(){
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
void print(int x){
    if(x<10)putchar(x+'0');
    else print(x/10),putchar(x%10+'0');
}
int main(){
    int n=read();
    for(int i=0;i<(1<<n);i++)a[bit(i)][i]=read();
    for(int i=0;i<(1<<n);i++)b[bit(i)][i]=read();
    for(int i=0;i<=n;i++)fwtor(a[i],n,1),fwtor(b[i],n,1);
    for(int k=0;k<=n;k++)for(int i=0;i<=k;i++)for(int x=0;x<(1<<n);x++)ad(c[k][x],1ll*a[i][x]*b[k-i][x]%p);
    for(int k=0;k<=n;k++)fwtor(c[k],n,-1);
    for(int i=0;i<(1<<n);i++)print((c[bit(i)][i]%p+p)%p),putchar(' ');
}

例题

ABC212H

模版题,可以容斥计算。

令 \(F(x)=\sum x^{A_i}\)

\[\begin{aligned}\\ &[x^0]\sum_{i=1}^NF^i(x)\\ &=[x^0]IFWT(\sum_{i=1}^NFWT(F^i(x))\\ &=[x^0]IFWT(FWT(\sum_{i=1}^NF^i(x)))\\ &=[x^0]IFWT(FWT(\sum_{i}x^i\sum_{t=1}^Nf_i^t)) \end{aligned} \]

等比数列计算最后 IFWT 回去即可。

注意特判 \(f_i=1\)

P5387 人形演舞

博弈论结合FWT,一般用于求方案数,可以先求出每个子游戏的 sg 函数。

打表看 sg 函数,发现 \(sg_x=x+1-2^{\lfloor\log_2x\rfloor}\),\(sg_0=0\)。

至于它要选出 \(|V|\) 个,本质上是求:

设 \(F(x)=\sum_{i=1}^m x^{sg_i}\),求 \(F^{|V|}(x)\) 的非项系数之和。

求出 \(FWT\) 之后再快速幂,然后 IFWT 即可。

州区划分

注意不连通是合法的

首先求出 \(sz_{S}=\sum_{x\in S}w_x\),设 \(g_S=[vaild(S)]sz_S^p\),至于不合法当且仅当图连通且具有欧拉回路,根据度数判断即可。

考虑dp,设 \(f_{S}\) 为当前已经用了的点的集合为 \(S\),显然有:

\[f_{S}=\frac{1}{sz^p_S}\sum_{T\subset S}f_Tg_{S/T} \]

考虑如何使用 \(fwt\) 优化稍加改动的子集卷积

注意到子集卷积的每一步有一个 \(|S|\),可以先做普通子集卷积,在做到 \(|S|\) 的时候将相应状态除掉 \(sz_S^p\) 再将 \(|S|\) 的部分加入卷积即可。

code

And-Or Game

题意:给定值域为正整数的集合 \(A,B\),你最初有一个数 \(V=0\),每次可以执行下列两种操作:

  1. 选择 \(x\in A,V\leftarrow V\lor x\),
  2. 选择 \(y\in A,V\leftarrow V\land x\)

你可以进行任意次操作,求可能达到的 \(V\) 的个数。

首先转化为表达方案数,我们合并连续的使用 \(A/B\) 的操作。也就是 \(A,B\) 自卷 \(|A|,|B|\),可以用 FWT 配合快速幂完成。

然后我们现在就是两个操作交替进行了,那么考虑一个答案是如何生成的,显然是在 or 时至少让某位的 0->1,在 and 时至少让某位 1->0,并且不会被抵消。

这就告诉我们最多不超过 \(\log V\) 次操作运算就封闭了,暴力交替操作判断操作前后可取数集合是否相同即可。

\(O(V\log^2 V)\)​,但跑不满。

code

CF582E

题面较长自行阅读。

根据输入显然知道要建立表达式树。直接用栈建就行了。

然后考虑我们设 \(f_{i,j}\) 为在子树 \(i\) 里,\(n\) 次操作的运算结果二进制压缩后是 \(j\)。

则可以预处理出单独每个字符的取值,在叶子节点的时候赋值。当如果是 ? 那就直接加上所有。

然后合并子树根据运算符类型用 fwtor fwtand 优化合并即可。问号就齐上。

二进制卷积优化DP转移

CF1326F2

很好的数学,使我的大脑旋转。

\(n\le 18\),给定 \(n\times n\) 矩阵 \(a_{i,j}\),保证 \(a_{i,j}=a_{j,i}\),考虑每个 \(1\sim n\) 的排列 \(p\),定义 \(01\) 串 \(s\),\(s_i=a_{p_i,p_{i+1}},|s|=n-1\)。问对于 \(2^{n-1}\) 种 \(01\) 串,生成其的排列个数各有多少。

注意到关键限制是 \(a_{i,j}\) 的值,直接做很困难。

考虑子集反演,本质上只考虑钦定某些位置为 \(1\),忽略掉 \(0\) 的限制。 设原本答案为 \(ans_i\),设 \(f_i=\sum_{i|j=j}ans_j\)。

则 \(ans_i=\sum_{j|i=j}(-1)^{(popcount(j\oplus i))}f_j\)。

\(O(n2^n)\)。

考虑计算 \(f\)。一个奇怪的发现是:对于 \(01\) 串的所有极长 \(1\) 段(带上前面的那个 \(0\)),将其整体移动到其他 \(0\) 的前面,不会使得这一段 \(1\) 变成零,而有可能使得 \(0\) 与 \(0\) 撞在一起形成新的 \(1\)。

这告诉我们,所有 \(f_i\),在 \(i\) 的二进制表示下,所有极长 \(1\) 段带上前面的 \(0\) 形成的长度可重集相同(我们默认第 \(-1\) 位,也就是 \(p_1\),是零)的时候,答案相同。注意这个结论

也就是例如 \(f(01110110)=f(01100111)=f(11011100)\),其可重集为 \(\lbrace 1,1,3,4\rbrace\),注意有个“不存在的 \(0\)”。

由此,我们发现答案至多有 \(18\) 的整数划分种,这玩意好像是三百多,约等于 \(18^2\)。

所以呢?这就有点子集卷积的味道了。

考虑对于每个 \(1\) 段计算答案。

设 \(dp_{S,i}\) 为经过 \(S\) 中所有点,最终停在 \(i\),且满足所有路径的边均为 \(1\) 的路径条数。

显然 \(dp_{S,i}·a_{i,k}\to dp_{S\cup\lbrace k\rbrace,k},dp_{\lbrace i\rbrace}{i}=1\)。

然后对 \(n\) 的每种整数划分求答案。

其实这个整数划分对应的是子集卷积,只不过钦定加入大小为多少的子集而已。

根据 \(FWT\) 优化子集卷积,可以先对所有大小的 \(|S|\) 进行 \(FWTOR\)。

然后在整数划分的过程中进行子集卷积,最后我们只关心全集的值,可以直接子集反演掉(FWTOR 本质是子集求和,这里逆差分就行)。

在求出每种情况的值之后就求得了 \(f\),然后反演回 \(ans\) 即可。

高维前缀和,高维差分,高维后缀和,FWTOR,FWTAND,FMTOR,FMTAND 本质与子集反演都是相通的。

code
#include<bits/stdc++.h>
using namespace std;
#define N 18
#define int long long 
// const int p=998244353;
#define bit __builtin_popcount
int f[(1<<18)+5],n,m,dp[(1<<18)+5][18],c[19][(1<<18)+5],dep,g[19][(1<<18)+5];
int rch[N];
void fwtor(int a[],int n,int tag){
    for(int len=1;len<(1<<n);len<<=1){
        for(int j=0;j<(1<<n);j+=len<<1){
            for(int k=0;k<len;k++){
                a[j+k+len]+=a[j+k]*tag;
                // a[j+k+len]%=p;
            }
        }
    }
}
map<vector<int> ,vector<int>>h;
vector<int>now;
void dfs(int sur,int lst){
    if(!sur){
        /*考虑到FWT or 的本质是高维前缀和,我们只要h[(1<<n)-1]那么这里做子集反演*/
        int res=0;
        for(int i=0;i<(1<<n);++i){
            if(bit(((1<<n)-1)^i)&1)res-=g[dep][i];
            else res+=g[dep][i];
        }
        // cout<<res<<"\n";
        for(auto i:h[now]){
            f[i]+=res;
            // cout<<" "<<i;
        }
        // cout<<"\n";
        return ;
    }
    for(int i=1;i<=min(lst,sur);i++){
        for(int j=0;j<(1<<n);j++)g[dep+1][j]=g[dep][j]*c[i][j];
        ++dep;now.push_back(i);
        dfs(sur-i,i);
        --dep;now.pop_back();
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);    
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            char x;cin>>x;
            if(x=='1')rch[i]|=(1<<j);   
        }
    }
    for(int i=0;i<n;i++)dp[1<<i][i]=1;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++)if((i>>j)&1)for(int k=0;k<n;k++)if(((i>>k)&1)^1){
            if((rch[j]>>k)&1)dp[i|(1<<k)][k]+=dp[i][j];    
        }
    }
    for(int i=0;i<(1<<n);i++)for(int j=0;j<n;j++)c[bit(i)][i]+=dp[i][j];
    for(int i=0;i<=n;i++)fwtor(c[i],n,1);
    for(int i=0;i<(1<<n-1);i++){//2^{n-1}种01串
        vector<int>now;
        int c=1;
        for(int j=0;j<n-1;j++){
            if((i>>j)&1)++c;
            else now.push_back(c),c=1;
        }
        now.push_back(c);sort(now.begin(),now.end());reverse(now.begin(),now.end());h[now].push_back(i);
    }
    for(int i=0;i<(1<<n);i++)g[0][i]=1;
    dfs(n,n);
    for(int i=0;i<n-1;i++)for(int j=0;j<(1<<n-1);++j)if((j>>i)&1)f[j^(1<<i)]-=f[j];
    for(int i=0;i<(1<<n-1);i++)cout<<f[i]<<" ";
}

ABC367 G

神奇题目

场上想到了引入多元生成函数之后就嗝屁了。

定义两个多项式的运算 \(A(z)*B(z)=\sum_{i}\sum_{j}z^{i\oplus j}a_ib_j\),也就是异或卷积。

定义两个二元生成函数 \(A(x,y)*B(x,y)=\sum_{i,p}\sum_{j,q}x^{i\oplus j}y^{p+q}a_{i,p}b_{j,q}\)

我们仍然选用 \(\prod\) 计算连续的 \(*\) 积

显然 \(k\) 很大,我们需要求出每个 \(xor\) 和的出现次数 \(c_i\)

而 \(c_i\) 可以简单的表示为:

\[C(z)=\sum_{i=1}z^i\left(\sum_{d=1}^{dm\le N}[x^iy^{dm}]\prod_{i=1}^n(1+x^{a_i}y)\right) \]

现在问题在于计算 \(\prod(1+x^{a_i}y)\)

这其实是 \(FWT\) ,而我们考虑计算其卷积,最后 \(IFWT\)

如果我们先不考虑 \(y\) 的影响,那么有 \(FWT(1+x^{a_i})=FWT(1)+FWT(x^{a_i})\) 计算结果中的第 \(j\) 项系数为 \(2[d(a_i\& j)=0]\),也就是二进制 \(\&\) 有偶数个 \(1\) 的位置为 \(2\),否则为 \(0\)。

根据这个我们可以计算 \(\prod(1+x^{a_i})\),具体的我们考虑一个 DP \(f_{i,0/1}\) 表示所有数中 \(\& i\) 有偶数/奇数个 \(1\) 的数的个数,还原每一项即可。事实上有 \(f_{i,0}+f_{i,1}=N\)

但是带上了 \(y\) 怎么办。实质上是把 \(y^{dm}\) 的项拿出来。对于 \(x^i\) 而言,如果 \(d(i\& j) =0\) ,那么就有选它,值增加一,或者不选它,如果 \(d(i\&j)=1\),就有选它,值减少一,或者不选它。选了的话选了的个数就会增加。

而 \(y\) 的实质是记录选了的个数,所以对应了 \((1+y),(1-y)\) 的两个决策。

所以实际上拿出 \(x_i\) 后 \(y\) 的系数是一个多项式 \((1+y)^{f_{i,0}}(1-y)^{f_{i,1}}\)。甚至我们可以据此定义广义的 \(FWT\)(第一维 \(xor\),第二维多项式积)

\[FWT_{ex}(F(x,y))=\sum z^j\sum_{i}(-1)^{d(i\& j)}f_{i,k}y^k \]

显然我们还是得到了一个二维多项式,且可以有 \(FWT_{ex}(1+x^{a_i}y)=\sum z^k+\sum_{z^k}{(-1)^{d(k\& a_i)}}y\)

也可以佐证上述结论。

所以我们对于每个 \(x^i\),拿出 \(y^{dm}\) 的系数后就可以做 \(IFWT\) 得到 \(C(z)\) 了。

怎么拿?不妨设 \(dp1_{i,j}\) 为 \((1+y)^i\) 中 \(y^{k},k\bmod m=j\) 的系数,\(dp2_{i,j}\) 为 \((1-y)^i\) 中 \(y^k,k\bmod m=j\) 的系数。

那么 \(\sum dp1_{f_{i,0},j}dp2_{f_{i,1},(-j)\bmod m}\) 就是所求系数。

code

ZJOI2019 开关

考场压根没有想 FWT

首先还是把 \(p_i\) 统一为概率,也就是 \(\sum p_i=1\)

设 \(f_S\) 为 \(a_i=[i\in S]\) 的答案,显然有:

\[\begin{cases} S&=\varnothing\implies f_{\varnothing}=0\\ S&\neq \varnothing\implies f_S=1+\sum p_if_{S\oplus \lbrace i\rbrace} \end{cases} \]

考虑 FWT。

设 \(F(x)=\sum f_Sx^S,G(x)=\sum p_ix^i\),显然有 \(G(1)=1\)。

有:

\[f_S=1+\sum p_if_{S\oplus \lbrace i\rbrace}\implies F(x)=\sum x^i+G(x)\times F(x)+k·x^{\varnothing} \]

注意这里的 $\times $ 代指异或卷积,且 \(\sum x^i\) \(i\) 的取值是空集到全集,由于 \(f_{\varnothing}\) 是不遵这个规则的所以需要插入修正常数

既然有异或卷积定然考虑 \(FWT\),不妨设 \(F'(x)=FWT(F(x)),G'(x)=FWT(G(x))\)

\[F'(x)=FWT(\sum x^i)+F'(x)·G'(x)+FWT(kx^{\varnothing}) \]

根据 \(FWT\) 定义,有 \([x^S]F'(x)=\sum(-1)^{|S\cap T|}[x^T]F(x)\)

\[\begin{cases} [x^S]FWT(\sum x^i)&=\sum [x^S]FWT(x^i)=\sum (-1)^{|S\cap i|}=2^{n-|S|}\sum_{S'\subseteq S}(-1)^{|S'|}=2^n[S=\varnothing]\\ [x^S]G'(x)&=\sum [x^S]p_iFWT(x^{\lbrace i\rbrace})=\sum(-1)^{|S\cap\lbrace i\rbrace|} p_i=1-2\sum_{i\in S}p_i\\ [x^S]FWT(k·x^{\varnothing})&=k \end{cases} \]

所以有

\[[x^S]F'(x)(1-G'(x))=2^n[S=\varnothing]+k=[x^S]F'(x)\sum_{i\in S}2p_i \]

由于 \(S=\varnothing\) 时,可以得到后式为零,因此有 \(k=-2^n\)

考虑 \(IFWT\) 回去,但是我们需要特别处理空集,有:

\[\begin{aligned} [x^S]F(x)&=[x^S]IFWT(F'(x))\\ &=\frac{\sum_{T}(-1)^{|S\cap T|}[x^T]F'(x)}{2^n}\\ &=\frac{[x^{\varnothing}]F'(x)}{2^n}+\frac{\sum_{T\neq \varnothing}(-1)^{|S\cap T|}[x^T]\frac{2^n[T=\varnothing]-2^n}{2\sum_{i\in T}p_i}}{2^n}\\ &=\frac{[x^{\varnothing}]F'(x)}{2^n}+\frac{\sum_{T\neq \varnothing}(-1)^{|S\cap T|}[x^T]\frac{-2^n}{2\sum_{i\in T}p_i}}{2^n}\\ \end{aligned} \]

又,我们需要知道 \([x^{\varnothing}]F'(x)\) 的值,但有 \([x^{\varnothing}]F(x)=f_{\varnothing}=0\),所以有:

\[[x^{\varnothing}]F'(x)=-\sum_{T\neq \varnothing}[x^T]\frac{-2^n}{2\sum_{i\in T}p_i} \]

回带有:

\[\begin{aligned} F(x)&=\frac{[x^{\varnothing}]F'(x)}{2^n}+\frac{\sum_{T\neq \varnothing}(-1)^{|S\cap T|}[x^T]\frac{-2^n}{2\sum_{i\in T}p_i}}{2^n}\\ &=\frac{-\sum_{T\neq \varnothing}[x^T]\frac{-2^n}{2\sum_{i\in T}p_i}}{2^n}+\frac{\sum_{T\neq \varnothing}(-1)^{|S\cap T|}[x^T]\frac{-2^n}{2\sum_{i\in T}p_i}}{2^n}\\ &=\frac{\sum_{T\neq \varnothing}((-1)^{|S\cap T|}-1)\frac{-2^n}{2\sum_{i\in T}p_i}}{2^n}\\ &=\sum_{|S\cap T|\bmod 2=1}\frac{1}{\sum_{i\in T}p_i} \end{aligned} \]

后面容易背包 \(O(nV)\) 解决。

标签:frac,运算,二进制,sum,IFWT,varnothing,FWT,卷积,合集
From: https://www.cnblogs.com/spdarkle/p/18295108

相关文章

  • mysql数据恢复--利用mysql二进制日志文件生成建表sql和数据恢复sql(文章末尾提供下载地
    ​ 近期误操作数据库,导致mysql表结构和数据都丢失了,为了恢复丢失的数据,自己写了个mysql数据库恢复软件。 ※※※※恢复原理(很简单)※※※※ 1.表结构恢复  使用ibd2sdi.exe工具,将mySql的二进制文件转换成txt;  分析txt文件内容,生成建表所用的create语句。 2.......
  • 二进制序列额运算
    二进制序列额运算题意:面对一个长度为n的数列a。∑(i,j,k,l=1~n)(a_iora_j)xor(a_kanda_l)结果对2^32取模思路:遇到相邻的数又加又减,大脑灵光一现,认为这题有规律可以找,于是乎,杨辉三角数就有了着落,一开始,使用暴力O(n^2)计算杨辉三角数,TLE了后来看了jzjr的题解,知道......
  • 红色警戒2+3游戏合集[共和国之辉][尤里的复仇][世界大战]
    当年爆款游戏红警2让很多人爱上了“建造游戏”有那么一些已经老去的产品,它们也许早已淡出人们的视线,但每每想到却令我们充满回忆。从90年代末到21世纪初的十几年,RTS(即时战略游戏)可以说是游戏市场最为火爆的一种类型,而红色警戒2(Command&Conquer:RedAlert2)绝对是玩家......
  • 51c大模型~合集13
     我自己的原文哦~  https://blog.51cto.com/whaosoft/11580286#SearchGPTOpenAI大杀器SearchGPT横空出世,单挑谷歌千亿美元搜索帝国OpenAI真来撼动谷歌的搜索帝国了?深夜悄悄上线的AI搜索引擎产品——SearchGPT,在同一问题的演示上,直接原地吊打谷歌和Perplexity。谷歌的AIO......
  • 二进制补码及与原码的互相转换方法详解
    在数字计算机系统中,数据的表示和处理是至关重要的一环。二进制作为计算机内部的基本编码方式,其表示形式直接决定了计算机处理数据的效率和准确性。在二进制表示中,原码和补码是两种重要的编码方式,尤其在处理有符号整数时显得尤为重要。本文将深入探讨二进制补码的概念、作用以及其......
  • 鲜花:基于位运算的 A+B Problem
    前置知识:二进制、按位与&、按位异或^、左移<<。按位异或的本质是二进制下不进位的加法,也就是对于每一位将值相加再直接对\(2\)取模。由于^和+有相同之处,考虑什么时候两者不同,很明显是二进制下需要进位的时候,那么什么时候需要进位呢?枚举可知,只有两个数该位都为\(1\)是该位需要......
  • 嵌入式课程day05-C语言运算符和选择结构
    4.8其他运算符自增自减:++--三目运算符:?:复合运算符:+= -=*=/=%= &= |=^= <<=>>=逗号运算符:,4.8.1自增自减:++--实现变量的+1或者-1操作++:单目运算符前置:++a后置:a++①如果++运算符作为单独语句使用++在前,++在后没有区别②如果++运算符参与其他......
  • javascript 基本语法,变量,运算符【知识点整理】
    JavaScript(ES5)JavaScript的基本语法和变量变量声明与变量赋值的方法:vara=5;vara=5;varb=4;vara=3,b=2;vara,b,c=5;vara=b=c=1;变量的命名规范首字符:英文和下划线组成:英文数字下划线禁忌:关键字、保留字##Unicode在HTML中,Unicode字符......