【OI之路】03数学-11集合幂级数

集合幂级数 或者你可以直接称其为 FWT

以下主要是学习笔记(vfk在15年的论文)和自己的一些实验

所以下面的内容请配合论文来看,不然你可能会自闭的

形式

集合幂级数 $f=\sum_{S \subseteq 2^U} f_S x^S$
加减法很好定义,对于乘除法,我们可以自行定义各种运算

集合并卷积(你也可以叫他子集反演)

核心思想:$[S_1 \bigcup S_2 \subseteq S]=[S_1 \subseteq S][S_2 \subseteq S]$

我们不妨称现在框里的形式为点值表达法;点值表达法很好求,简单dp即可,从高到低和从低到高是一样的;不过得出结果的点值后,怎么转化回去呢?

二项式定理可知$\sum_{s \in S} (-1)^{|s|}=[S=0]$ ,然后设f为原幂级数,g为点值表达法,然后反演来用g表达f
$$
g(n)=\sum_{m \in n}[n-m=0]g(m)=\sum_{m \in n} \sum_{s \in n-m}(-1)^{|s|}g(m)=\sum_{s \in n} (-1)^{|s|} \sum_{m \in n-s}g(m)=\sum_{m \in n} (-1)^{|n|-|m|} f(m)
$$
集合交也是类似的,就不赘述了

另一种理解思路,符号为 $g(S,k)$ 表示统计所有 $C_S T\in [1..k]$ 的子集T,从k=0开始dp,有些动态维护的题目需要这样表示(疯狂暗示其实是碰到过来加上的);然后如果这样完整表达,你按啥顺序dp都行,例如先第一维再第二维

那么加减乘都资瓷了,这个卷积的逆运算的话,就是在点值表达法下直接除
不能理解原理的话,把check写出来,不用运行你都会发现是正确的(指观察代码的形式,当然并没有考虑唯一性等问题)……所以说不定用二次剩余开根都行

###集合对称差卷积

$[S=\emptyset]=\frac{1}{2^n} \sum_{T \subseteq U} (-1)^{|T \bigcap S|}$
那么现在的式子就是 $B_S=\sum_{T \subseteq U} (-1)^{|T \bigcap S|} A_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放到中间去乘

子集卷积

或为S并为空,相当于两个不重叠集合的拼接,感觉不少状压都是这种形式
将条件转化为 $a \bigcup b=S且|a|+|b|=|S|$
可以看作是一个集合幂级数的或运算(异或也行)套一个形式幂级数的乘法,暴力枚举做即可,但要去除没有意义的地方(二进制与位长不符的地方)
然后逆运算的话,和上面思路不太一样(显然上面的方法不能再用了)
考虑每个位置在点值表达法下, $C_t=\sum A_i B_{t-i}$
那么现在求B的话可以递推,把其他B移到左边,除A0即可(经典的求递推方法)

经典题

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

bzoj5092 分割序列

先求出前缀异或值,然后就是 $S_j+(S_i \ xor \ S_j)$ ,当Si=1,怎么选都是1,否则如果Sj=1就是2,所以记录一个mask表示当前希望的Sj一定是mask的超集,所以fwt预处理好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]);
}
}

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