首页 > 其他分享 >P9745 「KDOI-06-S」树上异或 题解

P9745 「KDOI-06-S」树上异或 题解

时间:2023-10-16 17:35:11浏览次数:39  
标签:P9745 连通 06 int 题解 1ll times 异或 mod

P9745 「KDOI-06-S」树上异或 题解

\(x_i = 0\)

这题一看就不是很可做,先考虑部分分。

对于一条链的情况,我们可以枚举上一个断边的位置,然后转移。

一看数据范围,估计和值域有关,所以考虑 \(x_i = 1\) 的部分分,如果全部点权都是 1,那么一种方案只有 0 和 1 两种取值,考虑这个状态设计:\(f_{i, 0/1}\) 表示在以 \(i\) 为根的子树里面,\(i\) 的连通块异或值是 0/1,且除了 \(i\) 所在连通块其它连通块都是合法的 的连通块权值乘积的和。

然后转移就枚举每一个儿子选或不选即可,例如 \(f_{i,0}\) 可以这么转移,有点树上背包的味道:

\[f_{i,0} =\sum_{(i, v) \in E} f_{i,0}\times f_{v, 0} + f_{i, 1}\times f_{v,1} + f_{i,0}\times f_{v, 1} \]

分别表示选 \(v\),并且 \(v\) 的连通块异或和也是 \(0\);选 \(v\) 两个 \(1\) 异或起来是 \(0\);不选 \(v\),需要保证 \(v\) 子树内连通块合法。

思路

考虑把上述思路扩展到 \(x_i \ne 1\) 的情况。

用 \(f_{i, j, 0/1}\) 表示示在以 \(i\) 为根的子树里面,\(i\) 的连通块的第 \(j\) 位异或值是 0/1,且除了 \(i\) 所在连通块其它连通块都是合法的 的连通块权值乘积的和,再用一个 \(g_{i}\) 表示子树 \(i\) 内的连通块权值乘积的和。

\[f_{u,i,0} = \sum_{(i, v)\in E} f_{u, i, 0}\times g_v+f_{u, i, 0}\times f_{v, i, 0} + f_{v, i, 1}\times f_{u, i, 1} \]

最后用方案数乘上 \(2^{i}\) 就是这一位的贡献了,\(g_i\) 就可以通过 \(f\) 转移:

\[g_{u} = \sum_{i = 0}^{60}f_{u, i, 1}\times 2^i \]

代码

实现的时候要注意用临时变量存一下 \(f_{u, i, 0/1}\),防止环形转移。

另外由于每一条边 \((u,v )\) 都满足 \(u < v\),所以可以直接枚举边不用 DFS。

时间复杂度:\(O(n\log V)\)。

// Problem: P9745 「KDOI-06-S」树上异或
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-10-15 21:59:52

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
using namespace std;
const int N = 5e5 + 10, mod = 998244353;

int f[N][61][2], g[N], n;
long long a[N];
vector<int> G[N];

signed main() {
    n = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    for(int i = 2; i <= n; i ++) G[read()].push_back(i);
    for(int u = n; u; u --) {
        for(int i = 0; i < 60; i ++) f[u][i][a[u] >> i & 1] = 1;
        for(auto v : G[u]) {
            for(int i = 0; i < 60; i ++) {
                int a = f[u][i][0], b = f[u][i][1];
                f[u][i][0] = (1ll * f[u][i][0] * (g[v] + f[v][i][0]) + 1ll * f[v][i][1] * b) % mod;
                f[u][i][1] = (1ll * f[u][i][1] * (g[v] + f[v][i][0]) + 1ll * f[v][i][1] * a) % mod;
            }
        }
        for(int i = 0, p = 1; i < 60; i ++, p = p * 2 % mod) {
            g[u] = (1ll * g[u] + 1ll * p * f[u][i][1]) % mod;
        }
    }
    printf("%d\n", g[1]);
    return 0;
}

标签:P9745,连通,06,int,题解,1ll,times,异或,mod
From: https://www.cnblogs.com/MoyouSayuki/p/17767870.html

相关文章

  • [ARC167D] Good Permutation 题解
    题意对于一个长度为\(N\)的排列\(Q\),定义其为好的,当且仅当对于任意整数\(i\in\left[1,N\right]\),在进行若干次操作\(i\leftarrowQ_i\)后可以得到\(i=1\)。给定一个排列\(P\),定义一次操作为交换两个数。定义\(M\)为可以将\(P\)变为一个好的的排列的最小操......
  • 计算机网络的分组转发算法例题解析
    例题展示例题解决将题目中要求的ip地址与相对应的子网掩码进行二进制上面的相与即可,若是与目的ip地址一致,那么就直接跳转到其对应的那个接口;否则就直接跳转到默认接口;本题答案为R2;......
  • Gym101064L The Knapsack problem
    CF传送门发现物品的体积很小,尝试从此处入手。设\(K\)为最大的物品体积。把背包体积\(m\)分成差不超过\(K\)的两部分,然后合并。这样需要求出\(f(\frac{m}{2}-K\sim\frac{m}{2}+K)\)。递归地,可以发现需要求出\(f(\frac{m}{2^k}-K\sim\frac{m}{2^k}+K)\)。最......
  • UVA1366 Martian Mining 题解
    这个题可以用动态规划解决。令\(sbe_{i,j}\)为第\(j\)列\(1\)至\(i\)个格子\(BE\)矿总和,令\(snw_{i,j}\)为第\(i\)行\(1\)至\(j\)个格子\(NEW\)矿总和。\(dp_{i,j,0}\)表示为以第(\(i\),\(j\))为右下角,第(\(i\),\(j\))号格子建立\(BE\)矿管道的最大采矿量。\(dp......
  • P8854 [POI2002] 超级马 题解
    这题其实就是搜索,不知道怎么评绿的。题意有一个大小无限的棋盘,有一只马,给定\(n\)种跳法,判断马是否能跳到棋盘所有点。题解搜索马是否可以跳到他上下左右的四个点,因为只要能跳到这四个点,就可以以这四个点为基础跳到其他所有的点。这里有一些细节需要处理:因为每次操作能是......
  • CF1873E Building an Aquarium 题解
    这题看到第一眼就是二分。单调性二分最关键的东西是单调性在哪。单调性是如果高度越高,需要的水就越多,高度越矮,要用的水越少。不难得出代码:check函数:intcheck(intmid){ intsum=0; for(inti=1;i<=n;i++){ sum+=max(0ll,mid-a[i]); } if(sum<=x)returnsum; elsere......
  • BitBake使用攻略--BitBake的语法知识二(转载自https://www.cnblogs.com/chegxy/archive
    目录写在前面1.BitBake中的任务2.任务配置2.1依赖2.1.1内部任务间的依赖2.1.2不同菜谱下的任务间依赖2.1.3运行时态下的依赖2.1.4递归依赖2.1.5任务间的依赖2.2事件2.3校验和3.ClassExtensionMechanism 写在前面这是《BitBake使用攻略》系......
  • html2canvas 截图不全问题解决
    有个低代码平台项目,需求是要将canvas画布上的echarts图表等组件截图保存,如果是正常比例(也就是百分百比例)截图是正常的,但如果画布处于缩放状态进行截图的话就会因组件上的一些样式影响而导致截图不全。为了解决这一问题,在网上也查找了很多资料,终于找到解决办法,亲测有效。话不多说,......
  • 第二届“梦羽杯”题解
    前言特别鸣谢出(蒯)题人:CJYA原题:NOIP2008普及组T4《立体图》B原题:HAOI2007反素数C......
  • 题解 AcWing 1272. 与众不同
    题目描述定义完美序列:若一个序列内没有重复的数,称这个数列为完美数列。每次给定一个区间\([l,r]\),求这个区间内最长的完美序列长度。具体思路设\(len_i\)表示从\(i\)出发往右的最长完美序列长度。我们定义一个指针\(st\),表示当前枚举的区间左端点,同时定义多一个指针\(......