deepseek:

#include <cstdio>
#include <vector>
using namespace std;

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    
    int s5, s4, s3, s2, s1, p;
    scanf("%d %d %d %d %d %d", &s5, &s4, &s3, &s2, &s1, &p);
    
    int a3, a2, a1, b3, b2, b1;
    scanf("%d %d %d %d %d %d", &a3, &a2, &a1, &b3, &b2, &b1);
    
    // 计算每个节点的儿子数 s[i]
    vector<int> s(n + 1);
    for (int i = 1; i <= n; ++i) {
        long long x = i;
        long long res = s1 % p;
        long long term = x % p;
        res = (res + s2 * term) % p;
        term = (term * x) % p;
        res = (res + s3 * term) % p;
        term = (term * x) % p;
        res = (res + s4 * term) % p;
        term = (term * x) % p;
        res = (res + s5 * term) % p;
        s[i] = (int)res;
    }
    
    // 分配儿子区间 L[i], R[i] (若没有儿子则 L[i] = -1)
    vector<int> L(n + 1, -1), R(n + 1, -2);
    int cur = 2; // 下一个可用编号
    for (int i = 1; i <= n && cur <= n; ++i) {
        int k = s[i];
        int remain = n - cur + 1;
        if (k > remain) k = remain;
        if (k > 0) {
            L[i] = cur;
            R[i] = cur + k - 1;
            cur += k;
        }
    }
    
    // 迭代 DFS 计算进入/离开时间
    vector<int> dfn(n + 1), out(n + 1);
    vector<int> node_stack, next_child;
    node_stack.reserve(n);
    next_child.reserve(n);
    
    int timer = 0;
    dfn[1] = ++timer;
    node_stack.push_back(1);
    next_child.push_back(L[1] != -1 ? L[1] : -1);
    
    while (!node_stack.empty()) {
        int u = node_stack.back();
        int nc = next_child.back();
        if (nc == -1 || nc > R[u]) {
            out[u] = timer;
            node_stack.pop_back();
            next_child.pop_back();
        } else {
            int v = nc;
            dfn[v] = ++timer;
            next_child.back() = nc + 1; // 更新当前节点下一个儿子
            node_stack.push_back(v);
            next_child.push_back(L[v] != -1 ? L[v] : -1);
        }
    }
    
    // 回答询问
    int ans = 0;
    for (int i = 1; i <= q; ++i) {
        long long x = (1LL * a3 * i * i + 1LL * a2 * i + a1) % n + 1;
        long long y = (1LL * b3 * i * i + 1LL * b2 * i + b1) % n + 1;
        if (dfn[x] <= dfn[y] && dfn[y] <= out[x]) {
            ++ans;
        }
    }
    
    printf("%d\n", ans);
    return 0;
}

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 197ms

├ 测试数据 04：答案正确... 197ms

├ 测试数据 05：答案正确... 134ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：528ms

此题还不错，记录时间时间撮

这题的from。。。

离奇消失。。。

区间套定理....不是极限论里的吗，和这个有什么关系？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 353ms

├ 测试数据 04：答案正确... 353ms

├ 测试数据 05：答案正确... 338ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1044ms

来晚了啊！！！

2.找后代：

给定一棵树，判断X是否是Y的后代。

DFS，记录一个节点被访问到的时间和完成访问的时间l[i]和r[i]，j是i的后代 当且仅当l[i] < l[j] < r[i]

procedure dfs ( x : longint ) ;

begin

inc(cnt);

l[x] = cnt ;

for i = each son of x do dfs ( i )

inc(cnt);

r[x] = cnt;

end ;

这是区间嵌套定理。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 134ms

├ 测试数据 05：答案正确... 119ms

。。。。。。AC，发现是数组开小了。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 72ms

├ 测试数据 04：答案正确... 119ms

├ 测试数据 05：答案正确... 181ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：372ms

这样AC的，我是非常不明白我那个函数为什么会写错，看来还是pascal的问题，mod取余原来要那样分解就对了。算法真的没有什么。

算法参照LCA与RMQ，很快可以得到祖先的充要条件。

我想告诉LS一个事实，那就是子程序是存放于堆栈里的，如果你压了个巨大的数组进去当然就不行了