NC615 题解 | #不可思议#

题意分析

给出一棵树，然后我们给出若干个询问 $(x, y)$ ，对于每个询问，我们需要计算出 $\sum_{i为x到根路径上的点(包括x和根)}(y+2i)xor(y+i)$ .题目会给出输入输出的生成方法，按照题目描述操作即可。

思路分析

我们用迭代的方法进行操作，对于每个结点，我们记录下这个结点的父节点，然后一步一步的回退到当前结点的父节点，最后题目保证一定可以回退到1号结点，也就是根结点。

alt

如上图，对于每个询问，我们需要每次处理之后回退到它的父节点继续执行操作，直到到根节点。最后就可以得到答案了。
这里我给出两种不同语言版本的写法，他们的时间复杂度和空间复杂度都是一样的。
- 最坏的情况是树是一条链的情况，每次询问处理的时间复杂度为 $O (n)$ ,所有的询问的复杂度为 $O (n)$ 。最后，总的时间复杂度为 $O (n^{2})$
- 我们需要存储结点的父节点，空间复杂度为 $O (n)$

C++写法

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param seed1 long长整型 
     * @param seed2 long长整型 
     * @param seed3 long长整型 
     * @param x int整型 
     * @return long长整型
     */
    // 记录每个结点的父节点
    int fa[100010];
    // 计算从题目所求
    long long ans(int x,int y){
        long long sum=0;
        while(x!=1){
            sum+=(y+2*x)^(y+x);
            // 不断往父节点方向进行移动
            x=fa[x];
        }
        
        return sum+=(y+2)^(y+1);
    }
    long long work(int n, long long seed1, long long seed2, long long seed3, int x) {
        // write code here
        // 根据题目意思生成数据
        for(int i=1;i<=n;i++){
            long long seed4=(seed1+seed2)%998244353*seed3%998244353;
            fa[i+1]=(seed4%i+1);
            seed3=seed2;
            seed2=seed1;
            seed1=seed4;
        }
        
        long long ret=0,lastans=0,y=0,z;
        // 根据题目意思得到最后的结果
        for(int i=1;i<=n;i++){
            z=ans(x,y);
            ret=(ret+z)%998244353;
            lastans=z;
            x=((x+lastans)^ret)%n+1;
            y=lastans;
        }
        
        return ret;
    }
};

Go语言版

package main

/**
 * 
 * @param n int整型 
 * @param seed1 long长整型 
 * @param seed2 long长整型 
 * @param seed3 long长整型 
 * @param x int整型 
 * @return long长整型
*/
// 求解题目所求
func ans(x, y int64, fa []int64) int64 {
    var sum int64
    for {
        if(x==1){
            break
        }
        sum+=(y+2*x)^(y+x)
        // 利用迭代的思想进行求解，不断找父亲结点
        x=fa[x]
    }
    
    sum+=(y+2)^(y+1)
    return sum
}
func work( n int ,  seed1 int64 ,  seed2 int64 ,  seed3 int64 ,  x int ) int64 {
    // write code here
    fa := make([]int64, n+5)
    var i,m,xx int64
    // 先进行强制类型转换统一转换成int64型的
    m = int64(n)
    xx = int64(x)
    // 按照题目要求生成数据
    for i = 1; i < m; i ++ {
        var seed4 int64
        seed4=(seed1+seed2)%998244353*seed3%998244353
        fa[i+1]=seed4%i+1
        seed3=seed2
        seed2=seed1
        seed1=seed4
    }
    
    var lastans, ret, y int64
    lastans = 0
    ret = 0
    y = 0
    
    for i = 1; i <= m; i++ {
        z := ans(xx, y, fa)
        ret=(ret+z)%998244353
        lastans = z
        xx=((xx+lastans)^ret)%m+1
        y=lastans
    }
    
    return ret
}