【牛客编程巅峰赛S1第3场】不可思议

题目

给定一颗节点编号为 1~n 的，且以 1 为根的树，给出 n 组询问，每次询问给定一个数对 (x,y) ，求

对于这 n 组询问的答案，不需要依次输出 n 个数，只需要输出它们的和对 998244353 的取模即可。
树的信息以及询问不会直接给出，输入数据只包含随机种子，具体生成方式请仔细阅读备注内容。

备注：

输入数据包含5个整数，n,seed1,seed2,seed3,x.
树的信息生成伪代码如下
//////////////////////1/////////////////////
定义边集数组u[],v[]     //u[i],v[i]表示第i条边的两个端点
定义变量seed4
定义循环变量i从1到n-1
循环体开始
        seed4=(seed1+seed2)%998244353*seed3%998244353;
        u[i]=i+1;
        v[i]=(seed4%i)+1;
        seed3=seed2;
        seed2=seed1;
        seed1=seed4;
循环体结束
//////////////////////1/////////////////////
询问信息生成伪代码如下，顺带一提，第一次询问的x会在输入中给出
//////////////////////2/////////////////////
定义变量lastans，初始值为0           
定义变量ret，初始值为0
定义变量y，初始值为0          //含义见题干
定义函数ans(x,y)，返回值为对数对(x,y)这组询问的答案         //这里“询问”的含义见题干
定义变量z
定义循环变量i从1到n
循环体开始
        z=ans(x,y); 
        ret=(ret+z)%998244353;
        lastans=z;
        x=((x+lastans)^ret)%n+1;
        y=lastans;
循环体结束
//////////////////////2/////////////////////
输出一个整数，表示答案。
n<=10^5,seed1,seed2,seed3<=10^9,x<=n
保证构造出的数据合法。

解题思路

根据树的信息生成代码将每个节点的父节点记录 f。然后从当前的节点开始向上，直至根结点结束，根据题意计算异或和。

C++代码

class Solution {
    vector<int> f;    // 记录父节点

    long long ans(int x, int y){
        long long a = 0;
        int i = x;
        while(i!=1){
            a += (y + 2*i) ^ (y + i);
            i = f[i];
        }
        a += (y + 2) ^ (y + 1);    // 根节点
        return a;
    }

public:
    /**
     * 
     * @param n int整型 
     * @param seed1 long长整型 
     * @param seed2 long长整型 
     * @param seed3 long长整型 
     * @param x int整型 
     * @return long长整型
     */
    long long work(int n, long long seed1, long long seed2, long long seed3, int x) {
        // write code here

        f.resize(n+1, 0);

        // 树的信息生成
        for(int i=1; i<n; ++i){
            long long seed4 = (seed1 + seed2) % 998244353 * seed3 % 998244353;
            f[i+1] = (seed4 % i) + 1;
            seed3 = seed2;
            seed2 = seed1;
            seed1 = seed4;
        }

        // 询问信息生成
        long long ret = 0;
        int lastans = 0;
        int y = 0;
        for(int i=1; i<=n; ++i){
            long long z = ans(x, y);
            ret = (ret + z) % 998244353;
            lastans = z;
            x = ((x + lastans) ^ ret) % n + 1;
            y = lastans;
        }

        return ret;
    }
};