A simple Blog for wyx I've been down the bottle hoping.
HDU5909 Tree Cutting 树形dp+FWT
发表于: | 分类: Oi | 评论:0 | 阅读:57

题目大意:给出一棵树,每个点有一个点权,求对于每个$i\in[0,m)$输出有多少个连通诱导子图的异或和为i
$n\le 1000,m<2^{10}$

$f(x,y)$表示$x$节点在他的儿子里一通选最后异或和为$y$的方案数

转移显然,注意每个儿子都存在根本没选的情况就行了

考虑优化转移,注意到是$f(x,a)*f(y,b)$对应到$f(z,a\ xor b)$,直接fwt一波带走即可


#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+100;
const int mod=1e9+7;
const int inv2=(mod+1)>>1;

int val[N], F[N][N], ans[N], temp[N], len;
int n, m;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

vector<int> V[N]; 

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;
            }
}

void iFWT(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)*inv2%mod,a[i+j+d]=(1LL*(x-y)*inv2%mod+mod)%mod;
            }
}

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;
    iFWT(a,n);
}

void dfs(int x,int fa) {    
    F[x][val[x]]=1;
    for(int i=0;i<V[x].size();i++) {
        int v = V[x][i];
        if(v==fa) continue;
        dfs(v,x);
        for(int i=0;i<m;i++) temp[i]=F[x][i];
        solve(F[x],F[v],m); 
        for(int i=0;i<m;i++) (F[x][i] += temp[i]) %= mod;
    }

    for(int i=0;i<m;i++) (ans[i] += F[x][i]) %= mod;
}

int main()
{
    int t, x, y; 
    scanf("%d",&t);
    while(t--)
    {
        n = read(), m = read();
        memset(ans,0,sizeof ans);
        memset(F,0,sizeof F);
        for(int i=1;i<=n;++i) V[i].clear(); 
        for(int i=1;i<=n;++i) val[i] = read();

        for(int i=1;i<n;i++) {
            x = read(), y = read();
            V[x].push_back(y);
            V[y].push_back(x);
        }
        dfs(1,0);
        for(int i=0;i<m-1;i++)printf("%d ",ans[i]);
        printf("%d\n",ans[m-1]);
    }   
    return 0;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP