「OI之路」03数学-11集合幂级数

集合幂级数

一些记号同论文(vfk-15年)中一开始的约定

为了方便区分,暂且将集合并卷积、集合交卷积称为FMT,集合对称差卷积称为FWT

很多东西如果只是想写对复杂度是容易的(都是些基础dp),但这样没啥未来(比如我重写这破文章无数次了),最好知道式子是怎样的

如果对我这种数学理解不太感冒,可以看看师弟的

形式

集合幂级数 $f=\sum_{S \subseteq 2^U} f_S x^S$,其中$x^S$并没有实际意义
加减法很好定义,对于乘除法,我们可以自行定义各种运算(即定义$(f_Ax^A)(g_Bx^B)=f_Ag_Bx^{A \cdot B}$中的点是啥)

值得一提的是,因为无论怎么运算长度不变,所以可以做一些形式幂级数(生成函数那一套理论)做不到的事,例如以逆元为代表的,当初需要在模$x^N$意义下定义的各种操作

集合并卷积FMT

将运算定义为集合并,即$H_{S_1 \cup S_2}+=A_{S_1}*B_{S_2}$

集合并的核心性质:$[S_1 \cup S_2 \subseteq S]=[S_1 \subseteq S][S_2 \subseteq S]$

发现框里的东西很像当年学多项式卷积时的点值表达法,因为在那个意义下直接乘起来(因为成功拆分了)就行了

这启发我们实现$FMT:f’*S=\sum*{T \subseteq S} f_T$和$IFMT:FMT的逆运算$,熟练反演的选手可以知道IFMT就是$f_S=\sum_{T \subseteq S} (-1)^{|S|-|T|} f’_T$,不熟练的选手可以去反演与容斥那一章补习二项式反演、子集容斥

集合交也是类似的,就不赘述了

实现的理解、方法很多,不一一细说了,稍微值得一提的是 $g(S,k)$ 表示统计所有 $C_S T\in [1..k]$ 的子集T,这种写法可以写成第一层循环枚举S,第二层循环枚举数位(一般的写法就是这种的滚动版,但这种能做一些动态的问题,例如下面的度度熊)

集合并卷积的逆运算:将$A*B=C$两侧做FMT,那么就是在点值表达法下直接除,最后IFMT还原

子集卷积

不少状压都是这种形式(组合意义): $a \cup b=S且|a|+|b|=|S|$,也就是不重叠

将一个状态表示为$F=\sum_{i=0}^n A_ix^i$,其中Ai是个集合幂级数,定义其乘法为「或运算卷积+清除二进制与位长不符的地方」,外面相当于套着一个形式幂级数(称为占位幂级数)。两个状态的乘法就是对占位幂级数做乘法,暴力地$C_{i+j}+=A_i*B_j$即可。

子集卷积乘法模板loj152

对于各种操作,基本都是将等式两边做FMT得出等式(故无需考虑中途清除无意义位置),然后每个集合状态下是独立的,所以只需要考虑对占位幂级数做各种运算(也就是已经与集合幂级数无关了)

举个具体点的例子,$B=lnA=\int \frac{A’}{A}$,写成$B’*A=A’$,等式两边FMT,得到类似于$\sum_S (…)*(…) x^S=\sum_S (…)x^S$,多项式相等定义就是各系数相等,所以把系数取出来,得到等式

四则运算、求导和积分都是直接做(这里的求导和集合幂级数的求导是两码事),然后逆元、ln、exp的递推方式见多项式全家桶

例题:loj154 集合划分计数,所以强行在全家桶那边补充了下,完整code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
namespace FWT
{
void LN(vc<ll> &z,int n)
{
vc<ll> w(n+1);w[0]=z[1];assert(z[0]==1);
fo(i,1,n-1){ w[i]=z[i+1]*(i+1)%MOD;fo(j,1,i) add(w[i],MOD-z[j]*w[i-j]%MOD); }
z[0]=0;fo(i,1,n) z[i]=w[i-1]*Inv[i]%MOD;
}
void EXP(vc<ll> &z,int n)
{
vc<ll> w(n+1);w[0]=1;assert(z[0]==0);
fo(i,0,n-1){ fo(j,0,i) add(w[i+1],w[j]*z[i-j+1]%MOD*(i-j+1)%MOD);w[i+1]=w[i+1]*Inv[i+1]%MOD; }
z=w;
}
void kPOW(vc<ll> &z,int n,int k)
{
int pos=0;while(pos<=n and !z[pos]) pos++;if(pos*k>n or pos>n){ fo(i,0,n) z[i]=0;return; }//debug k=0
int val=z[pos],iv=invm(val);vc<ll> w(n-pos+1);fo(i,0,n-pos) w[i]=z[pos+i]*iv%MOD;
LN(w,n-pos);fo(i,0,n-pos) w[i]=w[i]*k%MOD;EXP(w,n-pos);
val=qpower(val,k);fo(i,0,n) z[i]=0;fo(i,0,n-pos) if(pos*k+i<=n) z[pos*k+i]=val*w[i]%MOD;
}
void kEXP(vc<ll> &z,int n,int k)
{
vc<ll> w(n+1);for(ll now=1,i=0;i<=k;i++,now=now*z[0]%MOD) add(w[0],now*facinv[i]%MOD);
vc<ll> c(n+1);c=z;kPOW(c,n,k);fo(i,0,n) c[i]=c[i]*facinv[k]%MOD;
fo(i,0,n-1){ fo(j,0,i) add(w[i+1],(w[j]+MOD-c[j])*z[i-j+1]%MOD*(i-j+1)%MOD);w[i+1]=w[i+1]*Inv[i+1]%MOD; }
z=w;
}
void fmt(ll f[],int n,int op=0){ fo(i,0,n-1) fo(s,0,bin(n)-1) if(s&bin(i)) op?add(f[s],MOD-f[s^bin(i)]):add(f[s],f[s^bin(i)]); }
const int B=21;ll h[B+1][bin(B)];
void solve(ll g[],ll f[],int n,int k)//change here
{
fo(ln,0,n) {fo(s,0,bin(n)-1) h[ln][s]=(ln==PC(s)?g[s]:0);fmt(h[ln],n);}
fo(s,0,bin(n)-1){
vc<ll> z(n+1);fo(ln,0,n) z[ln]=h[ln][s];
kEXP(z,n,k);//change here
fo(ln,0,n) h[ln][s]=z[ln];
} fo(ln,0,n) fmt(h[ln],n,1);fo(s,0,bin(n)-1) f[s]=h[PC(s)][s];
}
};

二进制FWT

UPD:学会K进制FWT后这部分的主要意义就是$f’*S=\sum*{T} (-1)^{|T \cap S|} f_T$这个式子

定义那个运算为集合异或,思考异或的性质,不知道如何发现$[S=\emptyset]=\frac{1}{2^n} \sum_{T \subseteq U} (-1)^{|T \bigcap S|}$

于是$H_{S}=\sum_{S1} \sum_{S2} [S1 \oplus S2 \oplus S=\emptyset] A_{S1}B_{S2} \to \frac{1}{2^n} \sum_{T} (-1)^{|T \cap S|} (\sum_{S1} (-1)^{|T \cap S1|} A_{S1})(\sum_{S2} (-1)^{|T \cap S2|} B_{S2})$

启发我们定义$FWT:f’*S=\sum*{T} (-1)^{|T \cap S|} f_T且IFWT:f_S=\frac{1}{2^n} \sum_{T} (-1)^{|T \cap S|} f’_T$

实现方法(显然只需实现一个函数):
考虑递推,$B[S][i]$表示当前只统计和S的异或值为 $2^i-1$ 的子集的T
那么每次把这一位不同、后面相同、前面任意的统计进去(然后你会发现自己没有被统计,应作为$B[S][-1]$)
$B[S][i]=B[S][i-1]-B[S|2^i][i-1],B[S|2^i]=B[S][i-1]+B[S|2^i][i-1]$
然后有个更简单的写法: $B[S][i]=B[S][i-1]+B[S|2^i][i-1],B[S|2^i]=B[S][i-1]-B[S|2^i][i-1]$
这个就不用前面那步了,本质上是一样的,因为 $B[S|2^i][i-1]$ 里面这一位都是1,等价于把-1放到中间去乘

K进制FWT

异或本质上是二进制的不进位加法,这里就是K进制不进位加法(用$\oplus$表示)

众所周知FFT有一种比较好的线性代数理解是,存在变换矩阵F,ABC是列向量,$\times$是点积,$(F*A) \times (F*B)=(F*C)$

对于第i行,把矩乘化开:$(\sum_{j=0}^{K^n-1} F_{i,j} A_j )*(\sum_{j=0}^{K^n-1} F_{i,j} B_j )=(\sum_{j=0}^{K^n-1} F_{i,j} C_j ) \rightarrow F_{i,z}=\sum_{x \oplus y=z} F_{i,x}F_{i,y}$

这个矩阵看似很大,但明显$F_{i,j}=\prod_{t=0}^{n-1} F_{ \frac{i}{K^t} \%K, \frac{j}{K^t} \%K }$,因此我们只需搞出$K*K$的矩阵。熟练的选手想必已经看出来了,此时就是个FFT,我们把当初推过的东西搬过来就完事了,$F_{i,j}=w_{K}^{ij},F^{-1}*{i,j}=\frac{w*{K}^{-ij}}{K}$

$F*A$的快速变换,就是每次把F的第i位加上去,$O(n*K^n*K)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ull t[10];struct Num
{
ull a[5];Num(){mem(a,0);}
ull& operator [] (int x){return a[x];}
void operator += (Num b){ fo(i,0,4) a[i]+=b[i]; }
void operator *= (ull b){ fo(i,0,4) a[i]*=b; }
Num operator * (Num b){ mem(t,0);fo(i,0,4) if(a[i]) fo(j,0,4) if(b[j]) t[i+j]+=a[i]*b[j];Num c;fo(i,0,4) c[i]=t[i]+t[i+5];return c; }
friend Num operator ^ (Num x,ull e){ Num ans;ans[0]=1;while(e){ if(e&1)ans=ans*x;x=x*x;e>>=1; } return ans; }
};
namespace kFWT
{
const int K=10,M=100000;Num B[M];
Num omega[K*K];void pre(){ omega[0][0]=1;omega[1][3]=-1;fo(i,2,K*K-1) omega[i]=omega[i-1]*omega[1]; }
void FWT(Num A[],int op=0)
{
for(int w=1;w<M;w*=K)
{
for(int up=0;up<M;up+=w*K)//枚举高位和低位
for(int i=0,ii=up;i<K;i++,ii+=w) for(int j=0,jj=up;j<K;j++,jj+=w)
{ Num om=omega[op?K-i*j%K:i*j%K];for(int dw=0;dw<w;dw++) B[ii+dw]+=om*A[jj+dw]; }
fo(x,0,M-1) A[x]=B[x],B[x]*=0;
}
}
};//CF1103E Radix sum

「HAOI2015」按位或
「WC2018」州区划分
雅礼冬令营集训2019 D8t1


计算$A_S=\sum_T B_TC_{S \cap T}$,$n\le20$

枚举并集T,根据集合反演(设f恰好g至少,$g_S=\sum_{S \subseteq T} f_T,则f_{S}=\sum_{S \subseteq T} (-1)^{|T-S|} g_T$),而计算「并集至少」是容易求的:
$$
A_S=\sum_{T \subseteq S} C_T*\sum_{T \subseteq T2} (-1)^{|T2-T|} [T2 \subseteq S] (\sum_{T2 \subseteq x} B_x)
\\
A_S=\sum_{T2 \subseteq S } (\sum_{T2 \subseteq x} B_x) (\sum_{T \subseteq T2} C_T*(-1)^{|T2-T|})
$$
三次FMT,对模数无要求

求$A_S=\sum_T B_TC_{S \cup T}$应该也类似

bzoj5092 分割序列

先求出前缀异或值,然后就是 $S_j+(S_i \ xor \ S_j)$ ,当Si=1,怎么选都是1,否则如果Sj=1就是2,所以记录一个mask表示当前希望的Sj一定是mask的超集,所以FMT预处理好f(S)表示S的超集最左边在哪里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[N],pp[1<<21];//超集
void main()
{
int n=qread();for(int i=1;i<=n;i++) a[i]=qread()^a[i-1];
memset(pp,0x3f,sizeof pp);for(int i=n;i>=1;i--) pp[a[i]]=i;pp[0]=0;
for(int j=0;j<=20;j++) for(int i=(1<<21)-1;i>=0;i--) if((i&bin(j))) chmin(pp[i^bin(j)],pp[i]);
for(int i=1;i<=n;i++)
{
int ans=0,mask=0;
for(int j=20;j>=0;j--)
{
if(a[i]&bin(j)) ans+=bin(j);
else if(pp[mask|bin(j)]<=i) mask|=bin(j),ans+=bin(j+1);
}
write2(ans);
}
}

一道类似的题:Manthan, Codefest 19 CF1208F Bits And Pieces


HDU6679 度度熊与运算式 2

首先转化题意,最大值一定是n+1,然后改异或的话要求不能进位即重叠,记$a_i$表示第i个?左边有多少个1,$a_{m+1}=n+1$ ,那么就是选一个集合要求最后一个元素是n+1且前面每个都是后面的子集

不难设计$dp(S)$ 表示以S为结尾的方案数,转移即 $dp(S)=\sum_{T \subset S}dp(T)$,考虑 $g(S)$ 表示S的子集和

因为要求这个必须求好前面,考虑类似分治fft的快速递推,考虑怎么动态做FMT,首先FMT如果要动态做,肯定要保留中间状态即上面所说的 $dp(S,k)$ 表示处理了k位,然后这种状态想怎么dp都行,考虑到现在是从小到大优化dp过程,所以先枚举第一维S,把$g(S)$给FMT出来,但如果当前是dp位置(即?处)的话,我们求出的只是 $dp(S)$ ,所以放到dp(S,0)处重新做一次FMT求出g

$O(n2^n)$ ,然而HDU的机子很慢,交比赛时myh的ac代码都会tle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
char str[N];int a[(1<<21)+4][22];
void main()
{
int T=qread();
while(T--)
{
scanf("%s",str+1);int n=strlen(str+1);
int mx=ceil(log2(n+2));a[0][0]=1;
for(int i=0;i<=n+1;i++)
{
//这里直接写成放进a[i][0]也行
if(i) a[i][0]=0;
for(int j=0;j<mx;j++) if(i&(1<<j)) a[i][j+1]=mm(a[i][j]+a[i^(1<<j)][j]); else a[i][j+1]=a[i][j];
if(i and i<=n and str[i]=='?')
{
a[i][0]=a[i][mx];
for(int j=0;j<mx;j++) if(i&(1<<j)) a[i][j+1]=mm(a[i][j]+a[i^(1<<j)][j]); else a[i][j+1]=a[i][j];
}
}
printf("%d %d\n",n+1,a[n+1][mx]);
}
}

UNR#2 黎明前的巧克力

题意:给出m个数,求$\sum_{不能同时空,不重叠子集A,B} [异或和相等]$

请先思考后再展开

$$
\sum_{子集S异或和=0} 2^{|S|}=[x^{\empty}] \prod_{i=1}^m (1+2x^{a_i}) (异或卷积)
\\
回忆FWT的式子:f’*S=\sum*{T} (-1)^{|T \cap S|} f_T,可知f’_{i,S}=1+(-1)^{|S \cap a_i|}*2
\\
ans
=IFWT_{\emptyset}
=\frac{1}{2^{bit}} \sum_S F_S
=\frac{1}{2^{bit}} \sum_S \prod_{i=1}^m (1+(-1)^{|S \cap a_i|}*2)
\\
设cnt_S个i满足|S \cap a_i|是奇数,
\frac{1}{2^{bit}} \sum_S (-1)^{cnt_S}*3^{m-cnt_S}
,只需考虑怎么求cnt_S
\\
用集合交FMT推一下,
cnt_S=\sum_T [|T|\&1] \sum_{T \subseteq ss}
(-1)^{|ss|-|T|} ([ss \subseteq S] \sum_{i=1}^m [ss \subseteq a_i])
\\
于是设
A_{ss}=(\sum_{i=1}^m [ss \subseteq a_i])*(\sum_{T \subseteq ss} (-1)^{|ss|-|T|}) [|T|\&1],
则cnt_S=\sum_{ss \subseteq S} A_{ss}
$$
发现A前面是个集合交FMT,后面是个集合并IFMT,乘起来后做个集合并的FMT就能得到cnt了

1
2
3
4
5
6
7
8
9
10
11
12
const int N=20;
void FMT1(ll A[]){ fo(i,0,N-1) fo(s,0,bin(N)-1) if(s&bin(i)) A[s]+=A[s^bin(i)]; }
void IFMT1(ll A[]){ fo(i,0,N-1) fo(s,0,bin(N)-1) if(s&bin(i)) A[s]-=A[s^bin(i)]; }
void FMT2(ll A[]){ fo(i,0,N-1) fo(s,0,bin(N)-1) if(s&bin(i)) A[s^bin(i)]+=A[s]; }
ll A[1<<N],B[1<<N];
void main()
{
int m=qread();fo(i,1,m) A[qread()]++;fo(s,0,bin(N)-1) B[s]=(PC(s)&1);
FMT2(A),IFMT1(B);fo(s,0,bin(N)-1) A[s]=A[s]*B[s]%MOD;FMT1(A);
ll ans=0;fo(s,0,bin(N)-1){ int cnts=A[s];add(ans,(cnts&1?MOD-1:1)*qpower(3,m-cnts)%MOD); }
write((ans*qpower(2,MOD-1-N)+MOD-1)%MOD);//记得减去同时空的方案
}

另外rose说他会常数项及后面那个任意系数,然后异或和任意单个位置的答案,复杂度不变

黎明前的巧克力之推广

题意:求$[x^{wt}]\prod_{i=1}^m (c_i+b_ix^{a_i})$,异或卷积,二进制位数不超过20

rose会与数域无关的做法,我只会实数域内输出前几位小数的;模数域内我还需要一个$m*\sqrt{MOD}$

请先思考后再展开

$$
ans=IFWT_{wt}=
\frac{1}{2^{bit}} \sum_{S} (-1)^{| wt \cap S |}
\prod_{i=1}^m (c_i+b_i*(-1)^{| a_i \cap S |})
\\
分别考虑交的奇偶性的积,
\frac{1}{2^{bit}} \sum_{S} (-1)^{| wt \cap S |} cnt_0(S)* cnt_1(S)
\\
cnt_1(S)=\prod_{i=1}^m (c_i-b_i) ^{\sum_T [|T|\&1] \sum_{T \subseteq ss}
(-1)^{|ss|-|T|} [ss \subseteq S] [ss \subseteq a_i]}
\\
cnt_1(S)=\prod_{i=1}^m (c_i-b_i) ^{
\sum_{ss} [ss \subseteq S][ss \subseteq a_i]
\sum_{T \subseteq ss} (-1)^{|ss|-|T|} [|T|\&1]
}
\\
cnt_1(S)=\prod_{i=1}^m (c_i-b_i) ^{
\sum_{ss} [ss \subseteq S][ss \subseteq a_i] V1_{ss}}
=\prod_{i=1}^m (c_i-b_i) ^{H_{S \cap a_i}}
=\prod_{T} F_T ^{H_{S \cap T}}
\\
取log转加法,cnt’*1(S)
=\sum*{T} F’*T *H*{S \cap T}
$$
问题转化成快速计算$A_S=\sum_T B_TC_{s \cap T}$,见前文

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f834.html
转载请注明出处,谢谢!