HDU 5909 FWT 加速集合异或

【题意】

Byteasar有一棵 $n$ 个点的无根树，节点依次编号为 $1$ 到 $n$ ，其中节点 $i$ 的权值为 $v_i$ 。

定义一棵树的价值为它所有点的权值的异或和。

现在对于每个 $[0, m)$ 的整数 $k$ ，请统计有多少 $T$ 的非空连通子树的价值等于 $k$ 。

一棵树 $T$ 的连通子树就是它的一个连通子图，并且这个图也是一棵树。

【解题思路】树形DP。DP[i][j]代表以i为根，异或结果为j的方案数，那么我们可以写出树形DP的大致结构如下：

这段代码里的solve，就是求两个集合异或的结果，明显我们暴力做是O(m * m)的，这里暴力做，加一些优化，例如读入挂等是可以莽过去这个题目的。但是这里有个更经典的加速集合异或的方法，FWT。复杂度可以降为O(m * logm)，我给出FWT的模板

const int rev = (mod + 1) >> 1; // FWT

void FWT(int a[],int n)
{
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++)
            {
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;
                //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;
                //and:a[i+j]=x+y;
                //or:a[i+j+d]=x+y;
            }
}

void UFWT(int a[],int n)
{
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++)
            {
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
                //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
                //and:a[i+j]=x-y;
                //or:a[i+j+d]=y-x;
            }
}

void solve(int a[],int b[],int n)
{
    FWT(a,n);
    FWT(b,n);
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;
    UFWT(a,n);
}

这个FWT模板的是非递归的形式，常数比递归少很多，还是可以学习的。

给出完整AC代码

//
//Created by BLUEBUFF 2016/1/10
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 1e3 + 100;
const int maxm = 100010;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
const double PI = acos(-1);
//head

//dp[u][i] 表示 u 为根的树，异或后得到i的方案数
int val[maxn], dp[maxn][maxn], ans[maxn], temp[maxn];
int n, m;
vector <int> G[maxn * 2];

void FWT(int a[],int n)
{
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++)
            {
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;
                //xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;
                //and:a[i+j]=x+y;
                //or:a[i+j+d]=x+y;
            }
}

void UFWT(int a[],int n)
{
    for(int d=1;d<n;d<<=1)
        for(int m=d<<1,i=0;i<n;i+=m)
            for(int j=0;j<d;j++)
            {
                int x=a[i+j],y=a[i+j+d];
                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
                //xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
                //and:a[i+j]=x-y;
                //or:a[i+j+d]=y-x;
            }
}

void solve(int a[],int b[],int n)
{
    FWT(a,n);
    FWT(b,n);
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;
    UFWT(a,n);
}

void dfs(int u, int fa)
{
    dp[u][val[u]] = 1; //自己与0异或后为 val[u] 的方案数
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v, u);
        for(int i = 0; i < m; i++) temp[i] = dp[u][i];
        solve(dp[u], dp[v], m); //当前dp[u]的所有值与dp[v]的所有值异或的结果
        for(int i = 0; i < m; i++) dp[u][i] = (dp[u][i] + temp[i]) % mod;
    }
    for(int i = 0; i < m; i++) ans[i] = (ans[i] + dp[u][i]) % mod;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &n, &m);
        CLR(ans, 0);
        CLR(dp, 0);
        REP2(i, 1, n) G[i].clear();
        REP2(i, 1, n) scanf("%d", &val[i]);
        REP1(i, 1, n){
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);
        for(int i = 0; i < m - 1; i++) printf("%d ", ans[i]);
        printf("%d\n", ans[m - 1]);
    }
    return 0;
}