FMT 和 子集卷积

FMT 和 子集卷积

FMT

给定数列$a_{0\dots 2^{k}-1}$求$b$满足$b_{s} = \sum_{i\in s} a_i$

实现方法很简单,

1
2
3
4
for( i in 0 to n-1 ) 
for( j in 0 to 2^n-1)
if( j & ( 1 << i ) )
a[j] += a[j ^ ( 1 << i )]

然后称为$B = \text{FMT}(A)$,快速莫比乌斯变换

想要还原也很简单,把代码反着写:

1
2
3
4
for( i in n-1 downTo 0 ) 
for( j in 2^n - 1 downTo 0)
if( j & ( 1 << i ) )
a[j] -= a[j ^ ( 1 << i )]

当然,$i$的顺序可以是原来的顺序,因为按照哪个顺序枚举位根本不重要

同时,$j$的顺序也不重要,考虑对于一个数字,它只有在当前枚举的位数为 1 的时候才被执行,所以就算已经枚举到这位是 0 的状态,它也不会被更新。

所以甚至只需要改个符号就是逆变换了

1
2
3
4
for( i in 0 to n-1 ) 
for( j in 0 to 2^n-1)
if( j & ( 1 << i ) )
a[j] -= a[j ^ ( 1 << i )]

这样$A = \text{IFMT}( B )$

FMT 可以写成 FFT 那样的形式,就不赘述了。

或卷积

或卷积就需要用到这个东西。

或卷积是指:

有一个结论,$\text{FMT}(C) = \text{FMT}(A) \cdot \text{FMT}(B)$,其中$\cdot$指点积,也就是把每个位置的函数值乘起来。

原因是$(i \cup j) \sube s$等价于$(i \sube s)\and(j \sube s)$。于是

所以有$\text{FMT}(C) = \text{FMT}(A) \cdot \text{FMT}(B) )$

于是可以$O(n2^n)$做这个。

子集卷积

子集卷积长这样:

如果设$p(x)$为$x$的 popcount( 1 的个数),那么:

我们把$C$扩展到二维,设$C’_{x,k}$,定义如下:

把$C$扩展到二维了,$A$也扩展到二维,定义$A’_{p,s}$

同理定义$b’_{x,s}$

我们知道

观察到$C’_x = \sum_{i=0}^x A’_{i}\times_{or} B’_{x-i}$,而且需要最后去掉左边的$p(s) \neq x$的情况。

这样复杂度$O(n^3 2^n)$,一共要卷$n^2$次。

注意$\text{FMT} , \text{IFMT}$都有可加性,所以我们把那个或卷积写成$\text{FMT}$的形式

我们现在只需要处理出所有$A’_i$和$B’_{i}$的 FMT ,最后再跑$n$次逆 FMT ,所以这样做就优化到了$O( 2^n n^2 )$

不知道为啥 开O2 TLE 了。。。注意模数是$10^9+9$不是$10^9+7$。。。目害成功wa了两发

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
using namespace std;
#define P 1000000009
int rd( ) {
char ch = ' '; int ret = 0;
while( ch > '9' || ch < '0' ) ch = getchar();
while( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' , ch = getchar();
return ret;
}

int A[1<<21] , B[1<<21] , n , len;
int a[21][1<<21] , b[21][1<<21] , c[21][1<<21];

void FMT( int A[] , int l ) {
for( int i = 0 ; i < l ; ++ i )
for( int j = 0 ; j < ( 1 << l ) ; ++ j )
if( j & ( 1 << i ) ) A[j] = ( A[j] + A[j ^ ( 1 << i )] ) % P;
}
void IFMT( int A[] , int l ) {
for( int i = 0 ; i < l ; ++ i )
for( int j = 0 ; j < ( 1 << l ) ; ++ j )
if( j & ( 1 << i ) ) A[j] = ( A[j] + P - A[j ^ ( 1 << i )] ) % P;
}

int main() {
cin >> n; len = ( 1 << n );
for( int i = 0 ; i < len ; ++ i ) A[i] = rd() , a[__builtin_popcount(i)][i] = A[i];
for( int i = 0 ; i < len ; ++ i ) B[i] = rd() , b[__builtin_popcount(i)][i] = B[i];
for( int i = 0 ; i <= n ; ++ i ) FMT( a[i] , n ) , FMT( b[i] , n );
for( int x = 0 ; x <= n ; ++ x ) {
for( int i = 0 ; i <= x ; ++ i )
for( int j = 0 ; j < ( 1 << n ) ; ++ j )
( c[x][j] += 1ll * a[i][j] * b[x - i][j] % P ) %= P;
IFMT( c[x] , n );
}
for( int i = 0 ; i < len ; ++ i ) printf("%d ",c[__builtin_popcount(i)][i]);
}
文章作者: yijan
文章链接: https://yijan.co/old65/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog