题目难度评测。

评测者	A	B	C	D	E	F	平均
出题人预期	$1600$	$1900$	$2200$	$2400$	$2800$	$3000$	$2316.67$
Tobo	$2500$	$1800$	$2400$	$0$	$3100$	$2600$	$2066.67$
YIZHIYANG	$2000$	$2100$	$2200$	$2400$	$2800$		$2383.33$
GPT-5 Thinking	$1700$	$2600$		$2500$	$3000$	$3400$	$2566.67$
平均	$1950.00$	$2100.00$	$2250.00$	$1825.00$	$2925.00$	$2950.00$	$2333.33$

A. 神秘算式

这道题本意是想作为 $1300$ 的签到，没想到一不小心出难了。

subtask 1

无脑暴力前缀和预处理即可，没什么好说的。

subtask 2

做法很多，这里只阐述标程的做法。

分块 + 多项式前缀和出奇迹。

本题的关键在于把 $i$ 按 $k=\lfloor\sqrt{i}\rfloor$ 分成长度 $2k+1$ 的整块。对同一块而言有 $i=k^{2}+j\;(0\le j\le2k)$，此时 $f(i)=(k^{3}+k+1)i-k$ 是关于 $j$ 的一次式，而满足背面条件的位置是等差序列 $j=m(k+1)$。因此块内全部牌面的总和可以写成六次多项式

$$\operatorname{blk}(k)=2k^{6}+3k^{5}+3k^{4}+5k^{3}+2k^{2}+\frac{k(k+1)^{2}}2\;( \bmod P) $$

再加上背面额外 $\sigma(i)=\tfrac{k(k+1)}2$。

只要能够在模 $P$ 下快速求出 $S_{d}(x)=\sum_{k=1}^{x}k^{d}\;(d\le6)$，整块前缀和就能 $O(1)$ 计算。把六次以内的 Faulhaber 公式直接展开，得到

补上高阶幂前缀和的闭式即可。Faulhaber 公式在 $d\le6$ 时写成分式分母很小，直接列出：

$$\begin{aligned} S_{1}(k)&=\frac{k(k+1)}2,\\[4pt] S_{2}(k)&=\frac{k(k+1)(2k+1)}6,\\[4pt] S_{3}(k)&=S_{1}(k)^{2},\\[4pt] S_{4}(k)&=\frac{k(k+1)(2k+1)\bigl(3k^{2}+3k-1\bigr)}{30},\\[4pt] S_{5}(k)&=\frac{k^{2}(k+1)^{2}\bigl(2k^{2}+2k-1\bigr)}{12},\\[4pt] S_{6}(k)&=\frac{k(k+1)(2k+1)\bigl(3k^{4}+6k^{3}-3k+1\bigr)}{42}. \end{aligned} $$

对应函数 s1∼s6，分母的逆元事先用快速幂算到 i2,i3,…,i42 中；tf(k) 就是把 $2S_{6}+3S_{5}+3S_{4}+5S_{3}+2S_{2}$ 按上述系数拼起来，得到前 $k\!-\!1$ 个完整块的贡献。

当 $n$ 落在块 $s$ 的中途时设 $r=n-s^{2}$。块内 $f(i)$ 对 $j$ 是等差数列，直接用等差求和公式得到

$$\bigl(k^{3}+k+1\bigr)\!\left[(r+1)s^{2}+\frac{r(r+1)}2\right]-s(r+1) $$

代码里的 $t1\cdot t2 - N\cdot sm$ 正是这一段。剩余的 $\sigma(i)$ 只会出现一到两次：必然有 $i=s^{2}$，若 $n\ge s^{2}+s+1$ 还需再加一次；对应函数 $sg(k)=\tfrac{S_{1}(k)+S_{2}(k)}2$，取 $k=s$ 和 $u=\left\lfloor\frac{\sqrt{4n-3}-1}{2}\right\rfloor$ 即可判断并补上。

整套流程每个测试点只做常数次整数运算，时间复杂度 $O(1)$。需要注意的是浮点开方仅用来给 $s$ 和 $u$ 提供初值，随后用两次 while 微调确保边界正确，因此在 $n\le10^{18}$ 时不会出错。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll P = 998244353;
ll ml(ll a, ll b)
{
    return (ll)((__int128)a * b % P);
}
ll pw(ll a, ll b)
{
    ll r = 1;
    while (b)
    {
        if (b & 1)
            r = ml(r, a);
        a = ml(a, a);
        b >>= 1;
    }
    return r;
}
ll i2, i3, i5, i6, i7, i12, i30, i42;
ll s1(ll k)
{
    k %= P;
    return ml(ml(k, (k + 1) % P), i2);
}
ll s2(ll k)
{
    k %= P;
    return ml(ml(ml(k, (k + 1) % P), (2 * k + 1) % P), i6);
}
ll s3(ll k)
{
    ll t = s1(k);
    return ml(t, t);
}
ll s4(ll k)
{
    k %= P;
    ll p2 = ml(k, k), p3 = ml(p2, k), p4 = ml(p2, p2), p5 = ml(p4, k);
    ll t1 = ml(p5, i5), t2 = ml(p4, i2), t3 = ml(p3, i3), t4 = ml(k, i30);
    ll r = (t1 + t2) % P;
    r = (r + t3) % P;
    r = (r + P - t4) % P;
    return r;
}
ll s5(ll k)
{
    k %= P;
    ll p2 = ml(k, k), p3 = ml(p2, k), p4 = ml(p2, p2), p5 = ml(p4, k), p6 = ml(p3, p3);
    ll t1 = ml(p6, i6), t2 = ml(p5, i2), t3 = ml(ml(p4, i12), 5), t4 = ml(p2, i12);
    ll r = ((t1 + t2) % P + t3) % P;
    r = (r + P - t4) % P;
    return r;
}
ll s6(ll k)
{
    k %= P;
    ll p2 = ml(k, k), p3 = ml(p2, k), p4 = ml(p2, p2), p5 = ml(p4, k), p6 = ml(p3, p3), p7 = ml(p6, k);
    ll t1 = ml(p7, i7), t2 = ml(p6, i2), t3 = ml(p5, i2), t4 = ml(p3, i6), t5 = ml(k, i42);
    ll r = (((t1 + t2) % P + t3) % P + t5) % P;
    r = (r + P - t4) % P;
    return r;
}
ll tf(ll k)
{
    if (k <= 0)
        return 0;
    ll r = (2 * s6(k)) % P;
    r = (r + 3 * s5(k)) % P;
    r = (r + 3 * s4(k)) % P;
    r = (r + 5 * s3(k)) % P;
    r = (r + 2 * s2(k)) % P;
    return r;
}
ll sg(ll k)
{
    if (k <= 0)
        return 0;
    return ml((s1(k) + s2(k)) % P, i2);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    i2 = (P + 1) / 2;
    i3 = pw(3, P - 2);
    i5 = pw(5, P - 2);
    i6 = pw(6, P - 2);
    i7 = pw(7, P - 2);
    i12 = pw(12, P - 2);
    i30 = pw(30, P - 2);
    i42 = pw(42, P - 2);
    int T;
    cin >> T;
    while (T--)
    {
        unsigned long long n;
        cin >> n;
        unsigned long long s = sqrtl((long double)n);
        while ((__int128)(s + 1) * (s + 1) <= n)
            ++s;
        while ((__int128)s * s > n)
            --s;
        unsigned long long r = n - s * s;
        ll ans = tf((ll)s - 1);
        ll sm = s % P, sp2 = ml(sm, sm), sp3 = ml(sp2, sm);
        ll N = (r + 1) % P, rm = r % P;
        ll t1 = (sp3 + sm + 1) % P;
        ll t2 = (ml(N, sp2) + ml(ml(N, rm), i2)) % P;
        ans = (ans + ml(t1, t2) + P - ml(N, sm)) % P;
        long double v = sqrtl((long double)4 * n - 3.0L);
        unsigned long long u = 0;
        if (v > 0)
            u = (unsigned long long)((v - 1.0L) / 2.0L);
        while ((__int128)(u + 1) * (u + 1) + (u + 1) + 1 <= n)
            ++u;
        while ((__int128)u * u + u + 1 > n)
            --u;
        ans = (ans + sg(s) + sg(u)) % P;
        cout << ans << '\n';
    }
    return 0;
}

---

B. 互质回响塔

关于前几个子任务的做法过多且过于简单，所以这里只讨论正解做法。

题目要求计算 $\sum_{i=1}^{n} k^{\,i}\,F\!\bigl(\lfloor n/i\rfloor\bigr)\bmod M$，其中 $F(m)=\sum_{j\le m}\varphi(j)$ 而 $\varphi$ 是欧拉函数。直接枚举会超时。

首先用线性筛在阈值 $c=\lceil n^{2/3}\rceil$ 内一次性求出 $\varphi$ 及其前缀和。对于 $m>c$ 的查询，套用 $\sum_{d\mid j}\varphi(d)=j$ 的狄利克雷卷积恒等式推导得递归式 $F(m)=\tfrac{m(m+1)}2-\sum_{l=2}^{m}(r-l+1)\,F(\lfloor m/l\rfloor)$，对同一 $m$ 只会访问 $O(m^{2/3})$ 个不同商，配合 unordered_map 做记忆化即可 $O(m^{2/3})$ 解决。听不懂么？听不懂就对了，请去学习“杜教筛”。

剩余部分利用除法分块，枚举左端 $l$，令 $q=\lfloor n/l\rfloor$、右端 $r=\lfloor n/q\rfloor$，区间 $[l,r]$ 内商恒为 $q$。这样只需 $O(\sqrt n)$ 个区间。对每段贡献，几何级数 $\sum_{t=0}^{r-l}k^{\,l+t}$ 可写成 $k^{\,l}\,\frac{k^{\,len}-1}{k-1}$，用快速幂和乘法逆元即可，$k\equiv1\pmod M$ 时特判结果为 $len$。

时间复杂度：杜教筛 $O(n^{2/3})$，除法分块 $O(\sqrt n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
const int MX = 5000005;
int ph[MX];
ll su[MX];
int pr[MX];
bool vs[MX];
int pc;
int lim;
void sie(int m)
{
    ph[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (!vs[i])
        {
            pr[pc++] = i;
            ph[i] = i - 1;
        }
        for (int j = 0; j < pc && 1LL * i * pr[j] <= m; j++)
        {
            int t = i * pr[j];
            vs[t] = 1;
            if (i % pr[j] == 0)
            {
                ph[t] = ph[i] * pr[j];
                break;
            }
            ph[t] = ph[i] * (pr[j] - 1);
        }
    }
    for (int i = 1; i <= m; i++)
        su[i] = su[i - 1] + ph[i];
}
unordered_map<ll, ll> mp;
ll cal(ll x)
{
    if (x <= lim)
        return su[x] % MOD;
    auto it = mp.find(x);
    if (it != mp.end())
        return it->second;
    ll res = ((__int128)x * (x + 1) / 2) % MOD;
    for (ll l = 2, r; l <= x; l = r + 1)
    {
        ll q = x / l;
        r = x / q;
        ll cnt = (r - l + 1) % MOD;
        res = (res - cnt * cal(q) % MOD + MOD) % MOD;
    }
    return mp[x] = res;
}
ll pwr(ll a, ll b)
{
    ll r = 1;
    while (b)
    {
        if (b & 1)
            r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}
int main()
{
    ll n, k;
    cin >> n >> k;
    lim = min((ll)MX - 5, (ll)pow((long double)n, 2.0 / 3.0) + 10);
    sie(lim);
    ll km = k % MOD, inv = 0;
    if (km != 1)
        inv = pwr((km + MOD - 1) % MOD, MOD - 2);
    ll ans = 0;
    for (ll l = 1, r; l <= n; l = r + 1)
    {
        ll q = n / l;
        r = n / q;
        ll len = r - l + 1;
        ll s = cal(q);
        ll g;
        if (km == 1)
            g = len % MOD;
        else
        {
            ll p1 = pwr(km, l);
            ll p2 = pwr(km, len);
            g = p1 * (p2 + MOD - 1) % MOD * inv % MOD;
        }
        ans = (ans + s * g) % MOD;
    }
    cout << ans << "\n";
    return 0;
}

---

C. 星岛双象

题意不再赘述。

subtask 1

保证原图无环，此时整段自由行走本质上只能形成一条从 $1$ 号点出发的有向路径，不可能回到已走过的点。因此直接在原图上做 DAG 上 DP 即可。

按原图拓扑序处理每条边 $(u\to v,w)$，维护 $dp[v][0],dp[v][1]$ 分别表示到达 $v$ 且当前状态为 $0/1$ 时，已能获得的最大能量。初始为 $dp[1][0]=0$、其余为 $-\infty$。

转移写成一行就是：对每条边、每个状态 $s\in\{0,1\}$，令 $t=s\oplus w$，更新 $dp[v][t]=\max\bigl(dp[v][t],\,dp[u][s]+([t=1]\cdot e_v)\bigr)$。

由于无环，若当前就能领那就立刻领，绝不会更差。处理完整个拓扑序后，答案取 $\max_v\max(dp[v][0],dp[v][1])$。套路地，正确性显然。

若更偏好拆点的写法，也可把每个点拆成 $(i,0)$、$(i,1)$ 两层，把 $(i,1)$ 赋权 $e_i$、$(i,0)$ 赋权 $0$，对每条原边连 $(u,0)\to(v,w)$、$(u,1)\to(v,1\oplus w)$ 两条边；原图无环保证拆点图同为 DAG，从源 $(1,0)$ 在拆点图上做一次带点权的最长路，得到与上述等价的答案。

时间复杂度 $O(n+m)$。

subtask 2/3

做法的核心是拆点 + 强连通分量缩点 + DAG 最长路 DP。把每个原节点 $i$ 拆成两个点 $(i,0)$ 与 $(i,1)$，分别表示到达 $i$ 且当前状态为 $0/1$。对原图一条边 $(u\to v,w)$，在拆点图中连两条边：$(u,0)\to(v,w)$ 与 $(u,1)\to(v,1\oplus w)$。这样任意行走与状态翻转被完全等价地编码在一张有向图上。因为只有状态为 $1$ 时才能收集点权，我们令 $(i,1)$ 的权为 $e_i$，$(i,0)$ 的权为 $0$。

由于允许在图上自由游走，只要身处某个强连通分量内部，就总能通过若干步访问到该分量内所有能收集的节点且不重复领取。因此将拆点图做强连通分量分解，把每个 SCC 的权定义为该分量内所有形如 $(i,1)$ 的点权之和，即 $\mathrm{wg}[C]=\sum_{(i,1)\in C} e_i$。随后把 SCC 缩成点，得到一张 DAG；在这张 DAG 上，从起点所在的分量 $s=\mathrm{SCC}(1,0)$ 出发做最长路型的 DP，转移为 $dp[v]=\max(dp[v],\,dp[u]+\mathrm{wg}[v])$，初值 $dp[s]=\mathrm{wg}[s]$。因为 DAG 无环，采用拓扑排序；答案取所有 $dp$ 的最大值。

正确性要点有二。其一，SCC 内可任意往返，且每个节点最多收一次，因此在一个 SCC 内能收集到的总收益恰等于该 SCC 的 $\mathrm{wg}$。其二，把任意一条原图上的游走投影到拆点图并再压到 SCC 序列后，跨分量的移动一定遵循 DAG 的有向边，且不可能回到先前的分量；所以任何可行方案对应于 DAG 上的一条从 $s$ 出发的有向路径，而能收集到的总收益就是路径上各点 $\mathrm{wg}$ 的和。最大收益因此等于 DAG 上以 $s$ 为源的最大路径权值，这正是上述 DP 求到的量。

实现上，拆出 $2n$ 个点与 $2m$ 条边；第一遍在正图上迭代 DFS 取后序序列，第二遍在反图上按逆序染色得到 $\mathrm{SCC}$ 并顺便累加每个分量的 $\mathrm{wg}$（仅当访问到奇状态点 $(i,1)$ 时加上 $e_i$）；随后按边跨分量关系建缩点 DAG 与入度；队列做拓扑，沿边松弛 DP；最后扫描 $\max dp$。起点设为 $(1,0)$ 所在分量，若该分量内部包含若干 $(i,1)$，它们会被一次性计入初值 $\mathrm{wg}[s]$。

时间复杂度 $O(n+m)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MV = 1000005;
const int ME = 4000005;

int n, m;
ll en[MV];

int hd[MV], to1[ME], nx1[ME], e1 = 0;
int h2[MV], to2[ME], nx2[ME], e2 = 0;
int h3[MV], to3[ME], nx3[ME], e3 = 0;
int in[MV];

void add1(int u, int v)
{
    to1[e1] = v;
    nx1[e1] = hd[u];
    hd[u] = e1++;
}
void add2(int u, int v)
{
    to2[e2] = v;
    nx2[e2] = h2[u];
    h2[u] = e2++;
}
void add3(int u, int v)
{
    to3[e3] = v;
    nx3[e3] = h3[u];
    h3[u] = e3++;
    ++in[v];
}

int st[MV * 2], od[MV], oc = 0;
char vs[MV];
int cp[MV], cc = 0;
ll wg[MV];
ll dp[MV];
int qu[MV];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> en[i];
    fill(hd, hd + 2 * n, -1);
    fill(h2, h2 + 2 * n, -1);
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        add1(u * 2, v * 2 + (w));
        add2(v * 2 + (w), u * 2);
        add1(u * 2 + 1, v * 2 + (w ^ 1));
        add2(v * 2 + (w ^ 1), u * 2 + 1);
    }
    for (int i = 0; i < 2 * n; i++)
        if (!vs[i])
        {
            int sp = 0;
            st[sp++] = i;
            while (sp)
            {
                int v = st[--sp];
                if (v >= 0)
                {
                    if (vs[v])
                        continue;
                    vs[v] = 1;
                    st[sp++] = ~v;
                    for (int e = hd[v]; e != -1; e = nx1[e])
                    {
                        int u = to1[e];
                        if (!vs[u])
                            st[sp++] = u;
                    }
                }
                else
                    od[oc++] = ~v;
            }
        }
    fill(cp, cp + 2 * n, -1);
    fill(h3, h3 + 2 * n, -1);
    for (int k = oc - 1; k >= 0; --k)
    {
        int v = od[k];
        if (cp[v] != -1)
            continue;
        int sp = 0;
        st[sp++] = v;
        cp[v] = cc;
        ll sum = 0;
        while (sp)
        {
            int x = st[--sp];
            if (x & 1)
                sum += en[x >> 1];
            for (int e = h2[x]; e != -1; e = nx2[e])
            {
                int y = to2[e];
                if (cp[y] == -1)
                {
                    cp[y] = cc;
                    st[sp++] = y;
                }
            }
        }
        wg[cc++] = sum;
    }
    for (int u = 0; u < 2 * n; u++)
        for (int e = hd[u]; e != -1; e = nx1[e])
        {
            int v = to1[e], cu = cp[u], cv = cp[v];
            if (cu != cv)
                add3(cu, cv);
        }
    fill(dp, dp + cc, -1);
    int sc = cp[0];
    dp[sc] = wg[sc];
    int fr = 0, bk = 0;
    for (int i = 0; i < cc; i++)
        if (!in[i])
            qu[bk++] = i;
    while (fr < bk)
    {
        int u = qu[fr++];
        for (int e = h3[u]; e != -1; e = nx3[e])
        {
            int v = to3[e];
            if (dp[u] != -1)
                dp[v] = max(dp[v], dp[u] + wg[v]);
            if (--in[v] == 0)
                qu[bk++] = v;
        }
    }
    ll ans = 0;
    for (int i = 0; i < cc; i++)
        if (dp[i] > ans)
            ans = dp[i];
    cout << ans << "\n";
    return 0;
}

---

D. 巡逻路径

很典的题目，练习点分治好题。灵感来源于 GESP 考场，这道题的原题数据范围只有 $1000$，但我赛时还是写了点分治。

subtask 1/2

直接搜即可，没啥好说的。

subtask 3

很自然地想到点分治，把经过该重心的最优路径一次性统计出来，再递归处理不经过该重心的部分，保证每条路径只在它的最高层重心处被统计一次。

在以某个重心 $c$ 为中心时，把所有从 $c$ 出发、沿着某个儿子子树延伸的简单路径看作一条臂。对每条臂，我们关心两件事：该臂上累计的黑点数 $b$（包含 $c$ 自身是否为黑），以及臂的长度 $d$（按节点数计，包含 $c$）。我们希望把来自不同子树的两条臂拼接，形成一条完整路径，同时满足黑点总数不超过 $K$。设另一条臂的黑点数为 $b'$。两臂相加时重心 $c$ 被计算了两次，所以总黑点是 $b+b'-\mathrm{bc}$（其中 $\mathrm{bc}=\mathbf{1}[c\ \text{是黑点}]$），约束为 $b+b'-\mathrm{bc}\le K$，等价于 $b'\le K-b+\mathrm{bc}$。

为了高效取最优，我们用树状数组按黑点数 $+1$ 建立索引，位置 $i=b'+1$ 处存放当前已处理过的子树里、黑点数不超过该索引的臂的最大长度。树状数组改为维护前缀最大值与单点取 $\max$ 更新，初值设为很小的负数代表不存在。处理流程为先查后加：对当前子树枚举得到的若干 $(b,d)$，先把可用黑点余量 $\mathrm{rem}=K-b+\mathrm{bc}$ 转成查询下标 $q=\mathrm{rem}+1$，从树状数组取出前缀最大长度 $\mathrm{best}$，尝试更新答案为 $d+\mathrm{best}-1$（两臂相接重心只算一次，所以减一）。随后再把这一子树的所有 $(b,d)$ 逐个以下标 $b+1$ 和值 $d$ 插入树状数组，供之后的兄弟子树查询使用，这样天然避免了同一子树内部两臂被错误拼接。为了同时覆盖单臂路径（只从重心往一个方向走），我们在开始时把仅包含重心的臂以 $(b=\mathrm{bc},\, d=1)$ 预先插入结构，此时查询到的 $\mathrm{best}=1$ 会把单臂的 $d$ 正确计入答案。

重心处对每个儿子子树做一次受限 DFS 即可枚举出 $(b,d)$ 集合，沿边时把下一个点颜色加到 $b$，一旦 $b>K$ 就直接剪枝；深度 $d$ 则随着步数加一。上述先查后加的顺序是保证不把同一子树内部的两条臂拼接；而补回 $\mathrm{bc}$ 即查询时用 $K-b+\mathrm{bc}$ 的原因，正是合并两臂时重心被重复计数需要纠正。整轮统计完成后需要把树状数组回滚清空，代码里用一个列表记录所有被更新过的下标，再按树状数组结构路径把对应节点重置为 $-\infty$，从而把均摊复杂度控制在可接受范围。

点分治部分是标准写法，先求子树大小找重心 $c$，在 $c$ 处完成上述统计，然后把 $c$ 标记为已分治，对所有未分治的儿子作为新的问题递归下去。由于每条路径只在其最高层重心处被统计一次，正确性成立。由于每个节点在整棵分治树上只参与 $O(\log N)$ 层，且每次参与时只会被 DFS 与树状数组以 $O(\log N)$ 的代价处理若干次。

时间复杂度 $O(N\log N)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int M = 200000 + 5;

int n, k;
int c[M];

int hd[M], ad[M * 2], nx[M * 2], ec;
bool v[M];
int s[M];
int a;

int bit[M];
int ui[M], uc;

int vb[M], vd[M], vc;

void add(int u, int w)
{
    ad[ec] = w;
    nx[ec] = hd[u];
    hd[u] = ec++;
}

void upd(int i, int val)
{
    for (; i <= n + 1; i += i & -i)
        bit[i] = max(bit[i], val);
}
int qry(int i)
{
    int r = -1e9;
    for (; i; i -= i & -i)
        r = max(r, bit[i]);
    return r;
}
void clb()
{
    for (int i = 0; i < uc; i++)
    {
        int x = ui[i];
        for (int j = x; j <= n + 1; j += j & -j)
            bit[j] = -1e9;
    }
    uc = 0;
}

int gs(int u, int p)
{
    s[u] = 1;
    for (int e = hd[u]; e != -1; e = nx[e])
    {
        int w = ad[e];
        if (w == p || v[w])
            continue;
        s[u] += gs(w, u);
    }
    return s[u];
}

int fc(int u, int p, int tot)
{
    for (int e = hd[u]; e != -1; e = nx[e])
    {
        int w = ad[e];
        if (w == p || v[w])
            continue;
        if (s[w] * 2 > tot)
            return fc(w, u, tot);
    }
    return u;
}

void col(int u, int p, int b, int d)
{
    vb[vc] = b;
    vd[vc] = d;
    vc++;
    for (int e = hd[u]; e != -1; e = nx[e])
    {
        int w = ad[e];
        if (w == p || v[w])
            continue;
        int nb = b + c[w];
        if (nb > k)
            continue;
        col(w, u, nb, d + 1);
    }
}

void sol(int rt)
{
    int tot = gs(rt, 0);
    int ct = fc(rt, 0, tot);
    v[ct] = 1;
    int bc = c[ct];
    if (bc <= k)
    {
        int idx = bc + 1;
        upd(idx, 1);
        ui[uc++] = idx;
        a = max(a, 1);
    }
    for (int e = hd[ct]; e != -1; e = nx[e])
    {
        int w = ad[e];
        if (v[w])
            continue;
        vc = 0;
        int ib = bc + c[w];
        if (ib <= k)
            col(w, ct, ib, 2);
        for (int i = 0; i < vc; i++)
        {
            int b = vb[i], d = vd[i];
            if (b > k)
                continue;
            int rem = k - b + bc;
            int qidx = rem + 1;
            int best = qry(qidx);
            if (best > -1000000000)
                a = max(a, d + best - 1);
        }
        for (int i = 0; i < vc; i++)
        {
            int b = vb[i], d = vd[i];
            if (b > k)
                continue;
            int idx = b + 1;
            upd(idx, d);
            ui[uc++] = idx;
        }
    }
    clb();
    for (int e = hd[ct]; e != -1; e = nx[e])
    {
        int w = ad[e];
        if (!v[w])
            sol(w);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    string s0;
    cin >> s0;
    for (int i = 1; i <= n; i++)
        c[i] = (s0[i - 1] == '1');
    fill(hd, hd + n + 2, -1);
    for (int i = 1; i < n; i++)
    {
        int u, w;
        cin >> u >> w;
        add(u, w);
        add(w, u);
    }
    fill(bit, bit + n + 2, -1000000000);
    sol(1);
    cout << a << "\n";
    return 0;
}

---

E. 环环相扣

仍然仅阐述正解做法。

这题的核心是先化简递推，得到闭式，再把期望写成对模 $k$ 余数分布的线性组合，最后用卷积在 $O(k\log k)$ 内求出该分布。

令 $i=k$。由定义可直接算出 $g(i,0)=\sum_{t=0}^{2i}[t\text{为偶数}]\cdot t=2(1+\cdots+i)=i(i+1)$。对一般列 $0\le j\le i-1$，把给出的转移带入并按列截断的规则整理，可用归纳证明 $g(i,j)=g(i,0)\binom{i-1}{j}$。验证边界 $i=1$ 显然成立；由递推把 $g(i-1,\cdot)$ 的线性组合化到第 $i$ 行后，系数满足帕斯卡恒等式，从而归纳成立。

于是对随机变量 $q\equiv Q(x)\bmod k$，有 $\mathbb{E}[g(k,q)]=g(k,0)\cdot \sum_{r=0}^{k-1}\binom{k-1}{r}\Pr[q=r]$，而 $g(k,0)=k(k+1)$。

因此问题等价于计算 $Q(x)=a(x^2)+b x+c$ 在模 $k$（其中 $k=2^t$）下的余数分布。发现是很简单的多项式入门题目。只需分别求出三项的模 $k$ 余数分布，然后做一次三项卷积即可。

记 $A\equiv x^2\bmod k,\;B\equiv x\bmod k$。对均匀 $a\in[1,n]$，余数 $aA\bmod k$ 的计数有明显的循环结构：设 $g=\gcd(A,k)$，映射 $a\mapsto aA\bmod k$ 只落在间隔为 $g$ 的 $k/g$ 个位置上，周期长度为 $\mathrm{per}=k/g$。把区间长度 $n$ 按整周期 $q=\lfloor n/\mathrm{per}\rfloor$ 和余数 $r=n\bmod \mathrm{per}$ 分解后，每个可达位置的基数都是 $q$，再从起点 $A\bmod k$ 顺着周期走 $r$ 步把多出来的 $1$ 次均匀分摊即可。同理可对均匀 $b\in[1,m]$ 的 $bB\bmod k$ 做同样的计数。常数项 $c\in[1,l]$ 则更简单：模 $k$ 的计数是把 $\lfloor l/k\rfloor$ 加到所有余数，再对前 $l\bmod k$ 个余数各加 $1$。这三份长度为 $k$ 的计数数组分别记为 $D_a,D_b,D_c$。

把三者做卷积得到 $Q(x)\bmod k$ 的计数。由于 $k=2^t\le 2^{21}$ 且模数 $p=998244353$ 的原根为 $G=3$，可直接用 NTT 在长度 $k$ 上做三次变换：先对 $D_a,D_b,D_c$ 各做一次 NTT，点值域逐点相乘，再做一次逆变换得到计数 $C[r]$（表示使 $Q(x)\equiv r$ 的三元组个数）。复杂度 $O(k\log k)$。实现里用快速幂计算单位根与逆元，并在逆变换末尾乘上 $n^{-1}$。注意只需要 $x\bmod k$，所以先把 $x$ 取模即可；当 $k=1$ 时，唯一的列是 $j=0$，答案直接是 $g(1,0)=2$。

期望的组合系数是 $\binom{k-1}{r}$。代码中用连乘式 $ \mathrm{co}[0]=1,\;\mathrm{co}[i]=\mathrm{co}[i-1]\cdot (k-i)\cdot i^{-1}$ 在线预处理得到所有 $\binom{k-1}{i}$（这里的 $i^{-1}$ 用费马小定理做逆元）。把逆 NTT 得到的 $C[r]$ 与 $\mathrm{co}[r]$ 做一次点积，得到 $\sum_r \binom{k-1}{r}\,C[r]$。设总样本数 $\mathrm{tot}=nml$，则答案为

$$\mathbb{E}[g(k,q)] \equiv k(k+1)\cdot \left(\sum_{r=0}^{k-1} \binom{k-1}{r}\,C[r]\right)\cdot \mathrm{tot}^{-1}\pmod p. $$

其中 $\mathrm{tot}^{-1}$ 取模逆，题面已保证 $n,m,l\bmod p\ne 0$ 从而可逆。这样把期望的问题完全降解为三段循环计数（用 $\gcd$ 与周期分摊）加一次 NTT 卷积与一次二项式线性组合。

时间复杂度 $O(k \log k)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;
const int G = 3;
const int N = 1 << 21;
int da[N], db[N], dc[N], co[N], iv[N];
ll pw(ll a, ll e)
{
    ll r = 1;
    while (e)
    {
        if (e & 1)
            r = r * a % P;
        a = a * a % P;
        e >>= 1;
    }
    return r;
}
void ntt(int *a, int n, int inv)
{
    for (int i = 1, j = 0; i < n; i++)
    {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;
        if (i < j)
            swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len <<= 1)
    {
        ll w0 = pw(G, (P - 1) / len);
        if (inv)
            w0 = pw(w0, P - 2);
        for (int i = 0; i < n; i += len)
        {
            ll w = 1;
            for (int j = i; j < i + len / 2; j++)
            {
                int u = a[j], v = (ll)a[j + len / 2] * w % P;
                a[j] = (u + v) % P;
                a[j + len / 2] = (u - v + P) % P;
                w = w * w0 % P;
            }
        }
    }
    if (inv)
    {
        ll ni = pw(n, P - 2);
        for (int i = 0; i < n; i++)
            a[i] = (ll)a[i] * ni % P;
    }
}
void clr(int *a, int n)
{
    memset(a, 0, n * sizeof(int));
}
ll gc(ll a, ll b)
{
    return b ? gc(b, a % b) : a;
}
void mk1(ll n, ll mul, int k, int *arr)
{
    clr(arr, k);
    mul %= k;
    if (!n)
        return;
    if (!mul)
    {
        arr[0] = n % P;
        return;
    }
    int g = gc(mul, k), per = k / g;
    ll q = n / per;
    int rem = n % per, base = q % P;
    for (int t = 0, idx = 0; t < per; t++, idx += g)
        arr[idx] = base;
    ll cur = mul % k;
    for (int i = 0; i < rem; i++)
    {
        arr[cur] = (arr[cur] + 1) % P;
        cur += mul;
        if (cur >= k)
            cur -= k;
    }
}
void mkc(ll L, int k, int *arr)
{
    ll b = L / k;
    int rem = L % k, base = b % P;
    for (int i = 0; i < k; i++)
        arr[i] = base;
    for (int i = 1; i <= rem; i++)
        arr[i] = (arr[i] + 1) % P;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    iv[1] = 1;
    for (int i = 2; i < N; i++)
        iv[i] = (ll)(P - P / i) * iv[P % i] % P;
    int T;
    T = 1;
    while (T--)
    {
        ll n, m, l, x;
        int k;
        cin >> n >> m >> l >> k >> x;
        if (k == 1)
        {
            cout << 2 << "\n";
            continue;
        }
        ll A = (x % k) * (x % k) % k, B = x % k;
        mk1(n, A, k, da);
        mk1(m, B, k, db);
        mkc(l, k, dc);
        ntt(da, k, 0);
        ntt(db, k, 0);
        ntt(dc, k, 0);
        for (int i = 0; i < k; i++)
            da[i] = (ll)da[i] * db[i] % P * dc[i] % P;
        ntt(da, k, 1);
        co[0] = 1;
        for (int i = 1; i < k; i++)
            co[i] = (ll)co[i - 1] * (k - i) % P * iv[i] % P;
        ll sum = 0;
        for (int i = 0; i < k; i++)
            sum = (sum + (ll)co[i] * da[i]) % P;
        ll f0 = (ll)k % P * (k + 1) % P;
        ll tot = ((n % P) * (m % P) % P * (l % P)) % P;
        ll ans = f0 * sum % P * pw(tot, P - 2) % P;
        cout << ans << "\n";
    }
    return 0;
}

---

F. 倒影之树

subtask 1

打一个 $O(n^3)$ 的暴力即可，非常朴素。

subtask 2

你会发现，两个串的 $lcp$ 就是 $LCA$ 的深度。

把所有串拿出来反着建 Trie。枚举点对求 $LCA$ 即可。

时间复杂度 $O(n^2)$。

subtask 3

问题变到了序列上，于是可以对于这个序列反过来建后缀数组，我们考虑枚举每一个位置作为靠前的那个位置计算答案。

根据数据的随机性，先建出 $height$ 数组的笛卡尔树，那么有一个结论是笛卡尔树的期望深度是 $\log n$，那么我们从后往前枚举这个位置，刚开始笛卡尔树为空，每次把当前这个位置的下一个位置插进树里去，同时在树上维护子树大小，然后对于当前这个询问，从对应的点不停向上跳，在跳的同时统计和他相对的那棵子树的答案即可。

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

subtask 4

核心利用随机性的期望上界，把与 $\operatorname{lcp}$ 有关的处理只做到很短的长度即可，同时 $\operatorname{lcs}(u,v)=\mathrm{dep}(\mathrm{LCA}(u,v))$ 天然给出乘子的另一因子，所以整题被化成按每个 LCA 统计两侧点对的 $\operatorname{lcp}$ 精确长度。

随机字符下，两串从各自节点向上比较，长度为 $t$ 的前缀相等的概率约为 $\Sigma^{-t}$（$\Sigma=256$）。于是全图里满足 $\operatorname{lcp}\ge t$ 的点对期望为 $O(n^2\Sigma^{-t})$，取 $t=\Theta(\log_\Sigma n)$ 时已趋近很小。实际实现中取一个安全上界 $L=\min\{50,\lceil\log_2 n\rceil\}$ 就够用，忽略 $t>L$ 的贡献在随机数据上有极高把握是零。

把每个节点 $x$ 当作 $LCA$ 来计数。若 $u,v$ 分别来自 $x$ 的两个不同儿子子树，则它们的 $\operatorname{lcs}$ 固定为 $\mathrm{dep}(x)$。令 $P_t(x)$ 表示这类点对中满足从各自节点向上长度为 $t$ 的前缀相等的对数；那么 $\operatorname{lcp}$ 恰为 $t$ 的对数是 $Q_t(x)=P_t(x)-P_{t+1}(x)$。对应贡献就是 $\sum_{t=1}^{L} t\cdot \mathrm{dep}(x)\cdot Q_t(x)$，把所有 $x$ 的贡献相加即为答案。

为在树上快速统计算法的相等前缀，先做一次倍增求祖先与多项式哈希的预处理。定义从根到 $v$ 的前缀哈希 $H[v]$ 满足 $H[v]=H[\mathrm{fa}(v)]\cdot B+c_v$，并预存 $B^k$ 和倍增表 $\mathrm{up}[v][j]$。于是从 $v$ 向上长度为 $t$ 的前缀（等价于根到 $v$ 路径的后缀长度 $t$）的哈希可在 $O(1)$ 取到：设 $a=\mathrm{kth\_anc}(v,t)$，则 $\mathrm{code}(v,t)=H[v]-H[a]\cdot B^t$（模意义下）。这样对任意两点 $u,v$，有 $\operatorname{lcp}\ge t$ 当且仅当 $\mathrm{code}(u,t)=\mathrm{code}(v,t)$。

统计 $P_t(x)$ 用树上启发式合并。对每个结点 $x$ 先递归处理所有儿子，其中把重儿子保留计数桶，其它轻儿子先查询后加入再清空。具体地，维护 $L$ 个哈希桶 $\text{cnt}[t][\cdot]$ 存储当前已合并子树中每个 $\mathrm{code}(\cdot,t)$ 的出现次数，同时为 $x$ 维护一组累加器 $\text{Sum}[t]$。当处理某个轻儿子子树时，枚举该子树的每个结点 $y$ 并对 $t=1\ldots\min(L,\mathrm{dep}(y))$ 查询 $\text{cnt}[t][\mathrm{code}(y,t)]$，把结果加到 $\text{Sum}[t]$ 得到跨子树且前缀长度 $\ge t$ 的新配对数；随后再把同一批 $y$ 的所有 $\mathrm{code}(y,t)$ 计入 $\text{cnt}$。轻儿子都并完后，$\text{Sum}[t]$ 就等于 $P_t(x)$。最后做一遍差分得到 $Q_t(x)=\text{Sum}[t]-\text{Sum}[t+1]$，把 $\sum_{t=1}^{L} t\cdot \mathrm{dep}(x)\cdot Q_t(x)$ 加入答案。

时间复杂度 $O(n\log^2 n)$。

subtask 5

关键在于把树上祖先串的比较转到一个可并的数据结构上。记 $S_v$ 为从 $v$ 向上到根的串，则 $\operatorname{lcs}(u,v)=\mathrm{dep}(\mathrm{LCA}(u,v))$。因此答案就是把所有以某个结点 $x$ 为最近公共祖先的点对 $(u,v)$ 的贡献累加，贡献为 $\operatorname{lcp}(u,v)\cdot\mathrm{dep}(x)$。难点只剩如何在全体节点之间高效拿到 $\operatorname{lcp}$。

由于字符集较大且是根向上的方向，不适合建后缀自动机，于是考虑在 Trie 上建立后缀数组。

于是两个点间的 $height$ 就是他们对应位置之间 $lcp$ 的最小值，和前面一样，还是建立 $height$ 数组上的笛卡尔树，它的深度也是期望 $\log_{\Sigma}$ 的，那么类似线段树合并，我们可以使用笛卡尔树合并，我们只要在合并的时候顺便计算跨过根节点的贡献就行了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 500010, LG = 19;
int n, fa[N], dep[N], ch[N], f[N][LG];

struct E
{
    int to, nx;
} eg[N];
int hd[N], ecnt;
inline void add(int a, int b)
{
    eg[++ecnt] = {b, hd[a]};
    hd[a] = ecnt;
}

int sa[N], rk0[LG][N], h[N], c[N], x1[N], x2[N], rk[N];

struct Tbl
{
    int hd[N], nx[N], vl[N], cnt;
    Tbl()
    {
        cnt = 0;
    }
    inline void add(int a, int b)
    {
        vl[++cnt] = b;
        nx[cnt] = hd[a];
        hd[a] = cnt;
    }
} tb;

void msa(int n, int m)
{
    int *p = x1, *q = x2, pv;
    for (int i = 1; i <= m; ++i)
        c[i] = 0;
    for (int i = 1; i <= n; ++i)
        ++c[p[i] = ch[i]];
    for (int i = 1; i <= m; ++i)
        c[i] += c[i - 1];
    for (int i = n; i; --i)
        sa[c[p[i]]--] = i;
    for (int i = 1; i <= n; ++i)
        rk0[0][i] = ch[i];
    for (int k = 1, j = 1; (1 << j) <= n; k <<= 1, ++j)
    {
        pv = 0;
        tb.cnt = 0;
        for (int i = 1; i <= n; ++i)
            tb.hd[i] = 0;
        for (int i = 1; i <= m; ++i)
            c[i] = 0;
        for (int i = 1; i <= n; ++i)
            if (dep[sa[i]] > k)
                tb.add(f[sa[i]][j - 1], sa[i]);
        for (int i = 1; i <= n; ++i)
            for (int t = tb.hd[sa[i]]; t; t = tb.nx[t])
                q[++pv] = tb.vl[t];
        for (int i = 1; i <= n; ++i)
            if (dep[i] <= k)
                q[++pv] = i;
        for (int i = 1; i <= n; ++i)
            ++c[p[q[i]]];
        for (int i = 1; i <= m; ++i)
            c[i] += c[i - 1];
        for (int i = n; i; --i)
            sa[c[p[q[i]]]--] = q[i];
        pv = 1;
        swap(p, q);
        p[sa[1]] = 1;
        for (int i = 2; i <= n; ++i)
            p[sa[i]] = (q[sa[i]] == q[sa[i - 1]] && q[f[sa[i]][j - 1]] == q[f[sa[i - 1]][j - 1]] ? pv : ++pv);
        for (int i = 1; i <= n; ++i)
            rk0[j][i] = p[i];
        m = pv;
    }
    for (int i = 1; i <= n; ++i)
        rk[sa[i]] = i;
}

int lcp(int a, int b)
{
    if (a == b)
        return dep[a];
    int res = 0;
    for (int i = LG - 1; i >= 0; --i)
        if (min(dep[a], dep[b]) >= (1 << i) && rk0[i][a] == rk0[i][b])
        {
            res += (1 << i);
            a = f[a][i];
            b = f[b][i];
        }
    return res;
}

pair<int, int> st[N][LG];
int lg[N];
pair<int, int> mn(pair<int, int> a, pair<int, int> b)
{
    if (a.first != b.first)
        return min(a, b);
    return (rand() & 1) ? a : b;
}
pair<int, int> qry(int l, int r)
{
    int L = lg[r - l + 1];
    return mn(st[l][L], st[r - (1 << L) + 1][L]);
}

int tot, trt, lc[N << 1], rc[N << 1], ln[N << 1];
ll mv[N];
int le[N];

void bld(int &rt, int l, int r)
{
    if (l == r)
    {
        rt = l;
        return;
    }
    rt = ++tot;
    int p = qry(l + 1, r).second;
    ln[rt] = qry(l + 1, r).first;
    for (int i = l; i < p; ++i)
        mv[i] = mv[i] * 2, ++le[i];
    bld(lc[rt], l, p - 1);
    for (int i = p; i <= r; ++i)
        mv[i] = mv[i] * 2 + 1, ++le[i];
    bld(rc[rt], p, r);
}

struct Nd
{
    int lc, rc, sum, l;
} t[N * 30];
int ptr, rt[N];
int nn()
{
    return ++ptr;
}
void ins(int k)
{
    rt[k] = nn();
    t[rt[k]].sum = 1;
    t[rt[k]].l = ln[trt];
    int cur = rt[k], cur2 = trt;
    k = rk[k];
    for (int i = le[k] - 1; i >= 0; --i)
    {
        if ((mv[k] >> i) & 1)
        {
            cur = t[cur].rc = nn();
            cur2 = rc[cur2];
        }
        else
        {
            cur = t[cur].lc = nn();
            cur2 = lc[cur2];
        }
        t[cur].sum = 1;
        t[cur].l = ln[cur2];
    }
}

const int MOD = 998244353;
int ans;
int mrg(int x, int y, int v)
{
    if (!x || !y)
        return x + y;
    ans = (ans + 1ll * v * t[x].l % MOD * t[t[x].lc].sum % MOD * t[t[y].rc].sum) % MOD;
    ans = (ans + 1ll * v * t[x].l % MOD * t[t[x].rc].sum % MOD * t[t[y].lc].sum) % MOD;
    t[x].sum += t[y].sum;
    t[x].lc = mrg(t[x].lc, t[y].lc, v);
    t[x].rc = mrg(t[x].rc, t[y].rc, v);
    return x;
}

void dfs(int k)
{
    for (int i = hd[k]; i; i = eg[i].nx)
    {
        dfs(eg[i].to);
        rt[k] = mrg(rt[k], rt[eg[i].to], dep[k]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    lg[1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        cin >> fa[i];
        add(fa[i], i);
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> ch[i];
        ++ch[i];
        dep[i] = dep[fa[i]] + 1;
    }
    for (int i = 1; i <= n; ++i)
        f[i][0] = fa[i];
    for (int k = 1; k < LG; ++k)
        for (int i = 1; i <= n; ++i)
            f[i][k] = f[f[i][k - 1]][k - 1];

    msa(n, 3);
    for (int i = 1; i <= n; ++i)
        st[i][0] = {h[i] = lcp(sa[i], sa[i - 1]), i};
    for (int k = 1, L = 1; k < LG; ++k, L <<= 1)
        for (int i = 1; i <= n - (L << 1) + 1; ++i)
            st[i][k] = mn(st[i][k - 1], st[i + L][k - 1]);

    tot = n;
    bld(trt, 1, n);
    for (int i = 1; i <= n; ++i)
        ins(i);
    dfs(1);
    cout << ans << "\n";
    return 0;
}