不可思议题解

【前言】
如题，不可思议。

【暴力】
模拟整个过程，O(n^2)级别。

【正解】
交了暴力居然过了...
其实出题人(wo)写的也是暴力，wo暂时没有找到除了暴力意外更优秀的做法，毕竟那个(y+i)xor(y+2i)，wo也不知道怎么变形成可以快速计算的形式。
观察题目，构造树和询问的方式几乎是无规律可循的，可将这个过程看做完全随机。
结论：
以1到n的顺序，每次等概率选择1到i-1中的一个点作为i的父亲，以此方式构造出来的树，树的深度是O(logn)级别的。
对于暴力地模拟这个过程，虽然看似是O(n^2)级别，但是严谨一点，上界应该是O(n*max(depth(x)))，即每次询问深度最大的点。
实际上由于随机的树深度在O(logn)级别，所以这个上界是O(nlogn)左右。
因此暴力的复杂度是O(nlogn)
要证明这个结论得话，设E(i)为第i个点的期望深度，假设1到i-1的点的深度分别为p[1],p[2],...，p[i-1]，那么第i个点的期望深度就是 ,那么由E(1)=1，直接推出整个数列，可以发现，E(i)=1+1/1+1/2+...+1/i-1，这个调和级数就是log2(n)级别的，得证~

【小结】
随机下，数据还是具备不少优美的性质的，当然这些性质也是随机的弱点，不过既然随机都有规律可循，那还能称之为随机吗(笑)

参考代码：

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param seed1 long长整型 
     * @param seed2 long长整型 
     * @param seed3 long长整型 
     * @param x int整型 
     * @return long长整型
     */
    int f[200000];
    long long ans;
    void up(int x,long long y)
    {
        while (x)
        {
            ans=ans+((y+x)^(y+2*x));
            x=f[x];
        }
    }
    long long work(int n, long long seed1, long long seed2, long long seed3, int x) {
        // write code here
        long long seed4;
        for (int i=1;i<n;i++)
        {
            seed4=(seed1+seed2)%998244353*seed3%998244353;
            seed3=seed2;
            seed2=seed1;
            seed1=seed4;
            f[i+1]=seed4%i+1;
        }
        long long lastans=0,ret=0;
        for (int i=1;i<=n;i++)
        {
            ans=0;
            up(x,lastans);
            ret=(ret+ans)%998244353;
            lastans=ans;
            x=((x+lastans)^ret)%n+1;
        }
        return ret;
    }
};