传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3696
【题解】
f[x][i]表示x节点子树，值为i的方案数。
暴力统计理论复杂度$O(nH^2)$。
按子树排序后统计复杂度好像还是错的。。但是能过
明天研究FWT。。
暴力跑了0.8s，FWT跑了3.1s。。。日
FWT也要按深度合并啊。。FWT的介绍在最后
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10, N = 1e5 + 10, H = 512 + 5; const int mod = 1e9+7; int n, f[N][H], g[N], par[N]; ll ans[H]; int t[N], tn; inline int cmp(int a, int b) { return g[a] < g[b]; } int head[N], nxt[N], to[N], tot = 0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } ll ss[H], tt[H]; inline void FWT(ll *a, int op, int L) { if(op) { for (int len=2; len<=L; len<<=1) { int m = len >> 1; for (ll *p = a; p != a+L; p += len) { for (int k=0; k<m; ++k) { ll x = p[k], y = p[k+m]; p[k] = (x+y)/2; p[k+m] = (x-y)/2; } } } } else { for (int len=2; len<=L; len<<=1) { int m = len >> 1; for (ll *p = a; p != a+L; p += len) { for (int k=0; k<m; ++k) { ll x = p[k], y = p[k+m]; p[k] = x+y; p[k+m] = x-y; } } } } } inline void FWT_combine(int *A, int an, int *B, int bn) { int L = 0, m = max(an, bn); while((1<<L) < m) ++L; m = (1<<L); for (int i=0; i<m; ++i) ss[i] = A[i], tt[i] = B[i]; FWT(ss, 0, m), FWT(tt, 0, m); for (int i=0; i<m; ++i) ss[i] = ss[i] * tt[i]; FWT(ss, 1, m); for (int i=0; i<m; ++i) ans[i] += ss[i]; } inline void dfs(int x) { int ret = 1; f[x][0] = 1; for (int i=head[x]; i; i=nxt[i]) dfs(to[i]); tn = 0; for (int i=head[x]; i; i=nxt[i]) t[++tn] = to[i]; sort(t+1, t+tn+1, cmp); for (int i=1; i<=tn; ++i) { int h = g[t[i]], y = t[i]; FWT_combine(f[x], ret, f[t[i]], h); for (int j=0; j<h; ++j) f[x][j] += f[y][j]; ret = max(ret, h); } for (int j=ret; j; --j) f[x][j] = f[x][j-1]; f[x][0] = 0; g[x] = ret + 1; } int main() { cin >> n; for (int i=2; i<=n; ++i) scanf("%d", par+i), add(par[i], i); dfs(1); for (int i=511; ~i; --i) if(ans[i] != 0) { for (int j=0; j<=i; ++j) printf("%lld ", ans[j]); return 0; } return 0; }
下面是暴力：
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10, N = 1e5 + 10, H = 512 + 5; const int mod = 1e9+7; int n, f[N][H], g[N], par[N]; ll ans[H]; int t[N], tn; inline int cmp(int a, int b) { return g[a] < g[b]; } int head[N], nxt[N], to[N], tot = 0; inline void add(int u, int v) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; } inline void dfs(int x) { int ret = 1; f[x][0] = 1; for (int i=head[x]; i; i=nxt[i]) dfs(to[i]); tn = 0; for (int i=head[x]; i; i=nxt[i]) t[++tn] = to[i]; sort(t+1, t+tn+1, cmp); for (int i=1; i<=tn; ++i) { int h = g[t[i]], y = t[i]; for (int j=0; j<ret; ++j) for (int k=0; k<h; ++k) ans[j ^ k] += 1ll * f[x][j] * f[y][k]; for (int j=0; j<h; ++j) f[x][j] += f[y][j]; ret = max(ret, h); } for (int j=ret; j; --j) f[x][j] = f[x][j-1]; f[x][0] = 0; g[x] = ret + 1; } int main() { cin >> n; for (int i=2; i<=n; ++i) scanf("%d", par+i), add(par[i], i); dfs(1); for (int i=511; ~i; --i) if(ans[i] != 0) { for (int j=0; j<=i; ++j) printf("%lld ", ans[j]); return 0; } return 0; }
===================================分割线==============================
考虑集合的位运算卷积
$C_i = sum_{j oplus k = i}A_jB_k$
每次只需要考虑最高位，事先补齐集合至2的次幂。
设符号$C = (A, B)$表示$C$由$A$和$B$顺次拼接而成。
如果只考虑最高位的话，有：
$ C = A oplus B = (sum_{j oplus k = 0} A_jB_k, sum_{j oplus k = 1} A_jB_k)$
（这里的0和1是因为值考虑最高位的原因）
这给了我们一个非常好的分治想法
假设我们构造出变换$f$以及逆变换$f_T$，满足：
$f(A)f(B) = f(C)$
那么我们就用类似于FFT的方法实现即可。
1. 如果是异或（xor）卷积的话：
$A_0$和$A_1$是按照$A$的最高位分成的两部分
$f(A) = (f(A_0) + f(A_1), f(A_0) - f(A_1))$
$f_T(A) = (f_T(frac{A_0 + A_1}{2}), f_T(frac{A_0 - A_1}{2}))$
正确性可以用归纳法证明。
其实只要记住正变换的式子即可，逆变换可以从正变换推导出来。
2. 如果是与（and）卷积的话
$f(A) = (f(A_0) + f(A_1), f(A_1))$
$f_T(A) = (f_T(A_0) - f_T(A_1), f_T(A_1))$
3. 如果是或（or）卷积的话
$f(A) = (f(A_0), f(A_1) + f(A_0))$
$f_T(A) = (f_T(A_0), f_T(A_1) - f_T (A_0))$