传送门
题意:
有一棵 n 个点的无根树, 节点依次编号为 1 到 n, 其中节点 i 的权值为 vi,
定义一棵树的价值为它所有点的权值的异或和
现在对于每个 [0,m) 的整数 k, 请统计有多少 T 的非空连通子树的价值等于 k
- Sample Input
- 2
- 4 4
- 2 0 1 3
- 1 2
- 1 3
- 1 4
- 4 4
- 0 1 3 1
- 1 2
- 1 3
- 1 4
- Sample Output
- 3 3 2 3
- 2 4 2 3
令 f[i][j]表示以 i 为根的子树中异或和为 j 的联通块个数, v 为 i 儿子
f[i][j]+=f[i][k]*f[v][l] (k^l==j)
发现转移其实可以写成这种形式:
$C_i=\sum_{j^k=i}A_j*B_k$
这和卷积有点类似, 不过运算改成了异或
这里就要用到 FWT(快速沃尔什变换)
链接 1
链接 2
就可以做到 nlogn 转移
转移完后记得在加上原来的 f[i][j], 因为你可以不选 v
复杂度为 $O(n^{2}logn)$
卡常, 少取模, 不要定义 long long 变量
这题还可以点分治
- #include < iostream > #include < cstdio > #include < cmath > #include < cstring > #include < algorithm > using namespace std;
- struct Node {
- int next,
- to;
- }
- edge[2501];
- int num,
- head[1501],
- Mod = 1e9 + 7,
- inv2,
- tmp[2001],
- a[1001][2001],
- ans[2001],
- n,
- m;
- int gi() {
- char ch = getchar();
- int x = 0;
- while (ch < 0 || ch > 9) ch = getchar();
- while (ch >= 0 && ch <= 9) {
- x = x * 10 + ch - 0;
- ch = getchar();
- }
- return x;
- }
- void add(int u, int v) {
- num++;
- edge[num].next = head[u];
- head[u] = num;
- edge[num].to = v;
- }
- int qpow(int x, int y) {
- int res = 1;
- while (y) {
- if (y & 1) res = 1ll * res * x % Mod;
- x = 1ll * x * x % Mod;
- y /= 2;
- }
- return res;
- }
- void FWT(int * A, int len) {
- int i,
- j,
- k;
- for (i = 1; i < m; i <<= 1) {
- for (j = 0; j < m; j += (i << 1)) {
- for (k = 0; k < i; k++) {
- int x = A[j + k],
- y = A[j + k + i];
- A[j + k] = x + y;
- if (A[j + k] >= Mod) A[j + k] -= Mod;
- A[j + k + i] = x - y + Mod;
- if (A[j + k + i] >= Mod) A[j + k + i] -= Mod;
- }
- }
- }
- }
- void UFWT(int * A, int len) {
- int i,
- j,
- k;
- for (i = 1; i < m; i <<= 1) {
- for (j = 0; j < m; j += (i << 1)) {
- for (k = 0; k < i; k++) {
- int x = A[j + k],
- y = A[j + k + i];
- A[j + k] = 1ll * (x + y) * inv2 % Mod;
- A[j + k + i] = 1ll * (x - y + Mod) * inv2 % Mod;
- }
- }
- }
- }
- void DP(int x, int y) {
- int i;
- for (i = 0; i < m; i++) tmp[i] = a[x][i];
- FWT(a[x], m);
- FWT(a[y], m);
- for (i = 0; i < m; i++) a[x][i] = 1ll * a[x][i] * a[y][i] % Mod;
- UFWT(a[x], m);
- for (i = 0; i < m; i++) {
- a[x][i] = a[x][i] + tmp[i];
- if (a[x][i] >= Mod) a[x][i] -= Mod;
- }
- }
- void dfs(int x, int pa) {
- int i;
- for (i = head[x]; i; i = edge[i].next) {
- int v = edge[i].to;
- if (v != pa) {
- dfs(v, x);
- DP(x, v);
- }
- }
- for (i = 0; i < m; i++) {
- ans[i] = ans[i] + a[x][i];
- if (ans[i] >= Mod) ans[i] -= Mod;
- }
- }
- int main() {
- int T,
- i,
- x,
- u,
- v,
- j;
- cin >> T;
- inv2 = qpow(2, Mod - 2);
- while (T--) {
- memset(head, 0, sizeof(head));
- num = 0;
- memset(a, 0, sizeof(a));
- memset(ans, 0, sizeof(ans));
- scanf("%d%d", &n, &m);
- for (i = 1; i <= n; i++) {
- x = gi();
- a[i][x] = 1;
- }
- for (i = 1; i <= n - 1; i++) {
- u = gi();
- v = gi();
- add(u, v);
- add(v, u);
- }
- dfs(1, 0);
- for (i = 0; i < m - 1; i++) printf("%d", ans[i]);
- printf("%d\n", ans[m - 1]);
- }
- }
- HDU 5909 Tree Cutting
来源: http://www.bubuko.com/infodetail-2491743.html