2019-07-20 10:22 已编辑西安电子科技大学后端工程师

关注

【2019牛客多校1 D】二项式展开+FWT原理

参考资料
https://ac.nowcoder.com/discuss/208861?type=101
https://zhuanlan.zhihu.com/p/41867199
http://blog.leanote.com/post/rockdu/TX20

题意

给定n,m,k,再给定n行m列数

$count[x] = \sum_{i=1}^n \prod _{j=1}^m [x \& a_{i,j} \text{的二进制表达式1的个数为奇数}]$

求

(修正：这里不是求和是异或和)

$\sum_{x \in [0,1<<k)} \frac 1 {2^m} count(x)\cdot 3^x$

分析

以下推导统一用&表示按位与，^表示按位异或

这题考察fwt_xor，但和常规的考察不太一样，它并不是构造式子做卷积，而是关于做FWT后，得到的向量与原向量关系的应用

深入理解FWT_XOR

walsh把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度。

我信号学得不好，不对上面内容进行理解，以下默认为竞赛应用

首先在这里我们姑且认为，我们需要快速计算

$C_x = \sum_{i \text{^} j = x} A_i B_j$

我们设数组A经过快速沃尔什变换之后记作

$FWT[A]$

做变换后满足

$FWT[C]_x = FWT[A]_x \cdot FWT[B]_x$

考虑到FWT[F] 的每一项是和原来的F线性相关的(因为是只有加减法)
所以可以设

$FWT[A]_x = \sum_{i=1}^n g(x,i) A_i$

那么我们就是要求

$\sum_{i=1}^n g(x,i) C_i = \sum_{j=0}^n g(x,j)A_j \cdot \sum_{k=0}^n g(x,k)B_k$ $\sum_{i=1}^n g(x,i) \sum_{j\text{^}k}A_jB_k = \sum_{j=0}^n g(x,j)A_j \cdot \sum_{k=0}^n g(x,k)B_k$

化简可得

$\sum_{j=0}^n \sum_{k=0}^n g(x,j\text{^} k) A_j B_k = \sum_{j=0}^n \sum_{k=0}^ng(x,j)g(x,k) A_j B_k$

这里我们可以看出

$g(x,j) g(x,k) = g(x,j \text{^}k)$

设 |x| = (x中1的个数)%2
因为

$|x\&j|+|x\&k| = |x \& (j\text{^}k)|$

因为所有系数绝对值大小相同，
所以我们可以确定

$g(x,i) = (-1)^{|i \& x|}$

也就是

$FWT(F)_x = \sum_{i=0}^n (-1)^{|i \& x|}F_i$

也就是每一个位置对于FWT[F]都有贡献，贡献正负由交集大小的奇偶性确定

题目分析

先考虑

$\prod _{j=1}^m [x \& a_{i,j} \text{的二进制表达式1的个数为奇数}]$

这部分可以写成

$\prod_{j=1}^m(1-(-1)^{|a_{i,j}\text{^}x|})$

即如果连乘式里有一个为偶数，整个式子结果为0

把连乘式展开，得
设S[x]为x个不同元素相加 $1-\sum (-1)^{S[1]} + \sum (-1)^{S[2]} - \sum(-1)^{S[3]}......$
我们知道

$|x\&j|+|x\&k| = |x \& (j\text{^}k)|$

所以上面的x个不同元素相加的每一项可以改写为

$(-1)^{|x\&(\text{^}_\in S)|} \cdot (-1)^{|S|}$

所以

$count(x) = \sum_{i=0}^{2^k-1} (-1)^{|x\& i|} \cdot f[i]$

这里的f数组即所有相同项的系数和

可以看出这就是沃尔什变换的表达式

所以我们对f数组做沃尔什变换就能够得到count数组

在这里我们需要预处理出来f数组，就枚举计算即可，在这里我用了dfs

代码

#include<bits/stdc  .h>
using namespace std;
const int N = (1<<20) 5;
int a[15];
int f[N];
int n,m,k;
const int mod = 1e9 7;

void dfs(int cs,int now,int base) {
    if(cs > m) {
        f[now] =base;
        return;
    }
    dfs(cs 1,now,base);
    dfs(cs 1,now^a[cs],-base);
}
void fwt(int a[],int m){
    int n = __builtin_ctz(m);
    for(int i=0;i<n;i  ) {
        for(int j=0;j<m;j  ) {
            if(j&(1<<i)) {
                int l = a[j^(1<<i)];
                int r = a[j];
                a[j^(1<<i)] = (l r)%mod;
                a[j] = (l-r mod)%mod;
            }
        }
    }
}
int qpow(int a,int b) {
    int res = 1;
    while(b) {
        if(b&1) res = res*1ll*a%mod;
        a = a*1ll*a%mod;
        b>>=1;
    }
    return res;
}
int main() {
    while(scanf("%d%d%d",&n,&m,&k)!=EOF) {
        int nk = (1<<k);
        for(int i=0;i<nk;i  ) f[i]=0;
        for(int i=1;i<=n;i  ) {
            for(int j=1;j<=m;j  ) {
                scanf("%d",&a[j]);
            }
            dfs(1,0,1);
        }
        fwt(f,nk);
        int base = 1,ans=0;
        int inv = qpow(1<<m,mod-2);
        for(int i=0;i<nk;i  ) {
            int now = f[i]*1ll*base%mod*inv %mod;
            ans ^= now;
            base = base*3ll%mod;
        }
        printf("%d\n",ans);
    }
}