Chlience

【题解】HDU 5909 Tree Cutting
Problem给定一棵 $n$ 个节点的树,每个节点有权值 $a[i]$求权值为异或和为 $k$ 的非空子图的数量...
扫描右侧二维码阅读全文
21
2019/02

【题解】HDU 5909 Tree Cutting

Problem

给定一棵 $n$ 个节点的树,每个节点有权值 $a[i]$

求权值为异或和为 $k$ 的非空子图的数量

Thought

设以 $x$ 为顶点的子树并且经过 $x$ 的子集异或和为 $y$ 的方案数为 $f[x][y]$
那么通过 $FWT$ 可以得到 $f[x][y\oplus a[x]]=\sum_{i\oplus j=y}f[u][i]*f[v][j]$

然后求个和就好了

#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1010;
const int M = 1 << 10;
const int mod = 1000000007;
const int inv2 = 500000004;
int val[N], a[N][M], ans[M];
int n, m;
struct Edge {
    int t, n;
}e[N << 1];
int head[N], tot;
void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}
void FWT_XOR(int* a, int f) {//f = 1 or - 1
    for(int l = 1 ; l < m ; l <<= 1)//the lenth of (L and R)
        for(int i = 0 ; i < m ; i += (l << 1))//the begin pos of L
            for(int j = i ; j < i + l ; ++ j) {//each pos
                int x = a[j], y = a[j + l];
                a[j] = (x + y) % mod; a[j + l] = (x - y + mod) % mod;
                if(f == - 1) {a[j] = 1ll * a[j] * inv2 % mod; a[j + l] = 1ll * a[j + l] * inv2 % mod;}
            }
}
void dfs(int x, int f) {
    ++ a[x][val[x]];
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == f) continue;
        dfs(e[i].t, x);
        ++ a[e[i].t][0];
        FWT_XOR(a[e[i].t], 1); FWT_XOR(a[x], 1);
        for(int j = 0; j < m; ++ j)
            a[x][j] = 1ll * a[x][j] * a[e[i].t][j] % mod;
        FWT_XOR(a[x], - 1);
    }
    for(int i = 0; i < m; ++ i)
        ans[i] = (ans[i] + a[x][i]) % mod;
}
void work() {
    tot = 0;
    memset(a, 0, sizeof(a));
    memset(ans, 0, sizeof(ans));
    memset(head, 0, sizeof(head));
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i)
        val[i] = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    for(int i = 0; i < m - 1; ++ i)
        printf("%d ", ans[i]);
    printf("%d\n", ans[m - 1]);
}
int main() {
    int t = read();
    while(t --)
        work();
    return 0;
}
Last modification:February 22nd, 2019 at 07:24 pm

Leave a Comment