• 浅谈集合幂级数


    叠甲:读者很菜。

    集合幂级数是一个很厉害的东西。

    我们对于是有限集的全集 U=1,2,n,我们利用占位符 xS 来表示一个序列 f,其中对于 SU 的值为 fS

    一般记为 F=SUfSxS

    对于占位符的运算,有 xS×xT={xST,ST=0,ST

    子集卷积

    我们考虑最基本的卷积运算:

    已知 F=SUfSxSG=SUgSxS 如何求解 H=F×G

    【模板】子集卷积

    如果运算有 xS×xT=xST,这就是普通的或卷积,可以 O(n2n) 实现。

    但是并不是,只有在 ST= 的时候才会做贡献,考虑在或卷积的基础上增加一些修改,使得其满足这个条件。

    我们知道 |S|+|T||ST|,取等的时候当且仅当 ST=,这就完美的满足了我们的条件。

    所以我们添加一个占位符 yxS 变成 xSy|S|,则 (xSy|S|)×(xTy|T|)=xSTy|S|+|T|,这样就完美的符合了我们的要求。

    具体的实现,就是增加以为,这一位的运算是朴素的多项式卷积。

    多项式卷积使用暴力算法可以做到 O(n22n),可以用 FFT/NTT 优化到 O(nlogn2n),但是常数太大,完全没有必要。

    void mul(int *F,int *G,int *H)
    {
    	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    	for(int i=0;ifor(int i=0;i<=n;i++) FMT(f[i]),FMT(g[i]);
    	for(int S=0;Sfor(int i=n;~i;i--)
    		{
    			g[i][S]=1ll*g[i][S]*f[0][S]%Mod;
    			for(int j=1;j<=i;j++)
    				add(g[i][S],1ll*f[j][S]*g[i-j][S]%Mod);
    		}
    	}
    	for(int i=0;i<=n;i++) iFMT(g[i]);
    	for(int i=0;i

    子集卷积 exp

    我们来考虑上面卷积运算的一些组合意义:

    如果我们想要查询有 f 中两个不交集合构成集合对应的方案数,其为 F×F2=F22

    依此类推选择 k 个构成的不交集合就是 Fkk!(除 k! 的原因是选择这些集合的相对顺序是无关的)。

    我们考虑选择若干个不交集合(考虑可以不选),有 G=x+k=1Fkk!

    发现 k=1Fkk!,这个东西就是 expF1。也就是说 G=expF

    因此,还是在 x 维上做或卷积,在 y 维上我们做多项式 exp,我们就可以通过 F 来生成 G=expF 了。

    G=expF,所以 G=(expF)

    所以 G=expF×FG=G×F

    iigiyi1=(igiyi)×(iifiyi1)

    所以 ngn=i=1nfi×gni。这样单次 exp 可以做到 O(n2),所以整体就可以做到 O(n22n)

    而子集卷积 exp 的组合意义就是:选择若干个不交集合组合在一起的所有方案

    void exp(int *F,int *G)
    {
    	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    	for(int i=1;ifor(int i=0;i<=n;i++) FMT(f[i]);
    	for(int S=0,tmp;S0][S]=1;
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=i;j++)
    				add(g[i][S],1ll*j*f[j][S]%Mod*g[i-j][S]%Mod);
    			g[i][S]=1ll*g[i][S]*inv[i]%Mod;
    		}
    	}
    	for(int i=0;i<=n;i++) iFMT(g[i]);
    	for(int i=0;i

    子集卷积 ln

    有 exp 就自然会有 ln。

    既然 exp 是组合,那么 ln 就是拆分。

    exp 是已知 f 得到 g,ln 就是通过 g 得到 f

    由于 ngn=i=1nfi×gni,所以 ngn=nfng0+i=1n1fi×gnig0=1)。

    fn=gn1ni=1n1fi×gni

    这样实现的复杂度也是 O(n22n) 的。

    组合意义就是:拆分成若干个不交集合

    void ln(int *F,int *G)
    {
    	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    	for(int i=1;i0][0]=1;
    	for(int i=0;i<=n;i++) FMT(f[i]);
    	for(int S=0,tmp;Sfor(int i=1;i<=n;i++)
    		{
    			g[i][S]=f[i][S],tmp=0;
    			for(int j=1;jadd(tmp,1ll*j*g[j][S]%Mod*f[i-j][S]%Mod);
    			del(g[i][S],1ll*tmp*inv[i]%Mod);
    		}
    	}
    	for(int i=0;i<=n;i++) iFMT(g[i]);
    	for(int i=0;i
  • 相关阅读:
    signal 处理函数使用
    Apache Doris的Bucket Shuffle Join实现
    小文件写入性能 5 倍于 S3FS,JuiceFS 加速生信研究
    Linux磁盘管理
    linux安装Ftp
    GBase 8c V3.0.0数据类型——序列号生成函数
    Java Web编程入门--spring boot + shiro
    安卓常见设计模式9------外观模式(Kotlin版)
    想用macbook录制视频?这几个技巧让你事半功倍!
    C#/.NET/.NET Core优秀项目和框架精选(坑已挖,欢迎大家踊跃提交PR或者Issues中留言)
  • 原文地址:https://www.cnblogs.com/Xun-Xiaoyao/p/18019800