Link.

今天的题解写得有点水, 没什么参考价值.

A. 出关 (laozi)

可以写出朴素的方程式:

$$ f_{i}+A_{s_i} \rightarrowtail f_{i+1} \\ f_i+B+k \times C \rightarrowtail f_{2i-k} $$

$\mathcal O(\frac {n^2}T)$. 其中 $T$ 是某个类似周期的数. 注意字符串是 0-indexed, 而 DP 数组是 1-indexed 的. 对第二个方程换元 $f_i + B + 2i \times C -(2i-k) \times C \rightarrowtail f_{2i-k}$, 令 $v_i = B + 2i \times C + f_i$, 则 $v_i - j \times C \rightarrow f_j$, 那么用线段树维护区间取 min, 单点求值, 标记永久化即可. 求范围需要求解 Z function.

B. 补天 (nvwa)

有点恶心. 首先, 合法的方案一共两种, 取决于第一个放置的颜色. 那么要统计的就是 $(i+j)\bmod 2 = 0$ 的位置数或 $(i+j)\bmod 2 = 1$ 的位置数. 先将所有区间离散化, 使用并查集维护连续段. 并查集的节点上再挂载一个 $cnt_{0/1}$, 分别表示连续段内符合上述两种条件的位置数. 再使用线段树维护区间内... [咕]

C. 理水 (dayu)

发现以前根本没做过正经换根 DP.

先对原图进行边双缩点, 得到一棵树. 如果一个边双连通分量里面存在一条 $1$ 边, 则经过该点的路径均为合法路径. 对于固定的根节点, 设 $f_u$ 表示从 $u$ 出发, $u$ 的子树里的合法节点数. 然后换根即可.

D. 非攻 (mozi)

高一学弟的做法非常简洁, 很有水平! 以下就是他的做法.

考虑固定排列 $P = (p_1, \dots, p_n)$, 连边 $i \rightarrow p_i$, 解决交换次数最小的限制很容易, 注意到每次操作最多让一个环里面的节点变成自环即可. 然后是代价最小的限制, 一个下界是 $\displaystyle \sum m_i(s_i-m_i)$ 其中 $m_i$ 和 $s_i$ 分别表示第 $i$ 个环的最小值和权值和. 手玩发现, 一次交换使一个点变成自环, 剩下的点构成一个新环, 因此这个下界总是取得到.

接下来解决计数. 对一对数 $(i, j)$, 考虑 $i \times j$ 对答案的贡献次数, 这对数对答案产生贡献当且仅当:

• $i$ 是环中最小值;
• $i$ 和 $j$ 在同一环里.

进行构造:

1. 把前 $i-1$ 个数放进图里, 这部分可以随意放, 方案数 $(i-1)!$;
2. 把 $i$ 放进来, 由于 $i$ 是最小值, 因此 $i$ 只能构成一个新环, 方案数 $1$;
3. 把 $j$ 放进和 $i$ 同一环里, 因为此时环里仅有 $i$ 一个元素, 方案数 $1$;
4. 把 $(i, j)$ 和 $(j, n]$ 中的数放进来, 这部分可以随意放, 方案数 $\frac{n!}{(i+1)!}$.

整理以下, 答案就是 $\displaystyle \sum_i \sum_j ij\times \frac{n!(i-1)!}{(i+1)!}$, 预处理阶乘计算即可.

/ 如在黑夜中 被熄灭了星空 /

/ 荒原上看不到尽头 /

/ 只有这一路相随的孤独 /

/ 是我黑暗中唯一的盟友 /

—— Kide - 光 ft. 星尘

Desc.

Link.

有 $n$ 个二元组, 用 $(a_i, t_i)$ 描述. 等概率在 $[1, k] \bigcap \mathbb{N}^*$ 中选取一个 $x$, 执行以下操作 $x$ 次:

• 取一空数组 $\{b_n\}$, 令 $\displaystyle b_i = \sum_{t_j = i} a_j$, 然后再用 $b_i$ 替换每个 $a_i$;

问最终 $a_i$ 的期望值对 $\mathbf{998244353}$ 取模的结果;

$1\leqslant n \leqslant 2 \times 10^5$, $1 \leqslant k \leqslant 10^{18}$, $k$ is not a multiple of $\mathbf{998244353}$.

Sol.

令 $\mathbf A = \left( \begin{matrix} a_1, \dots, a_n \end{matrix}\right)$, $\mathbf T = \left (\begin{matrix} 0/1 & \cdots & 0/1 \\ \vdots & \ddots & \vdots \\ 0/1 & \cdots & 0/1 \end{matrix}\right)$, 其中 $\mathbf T_{i, t_i} = 1$, 其余为 $0$. 则答案为 (以下均省去 $\frac 1k$ 不写):

$$ f(\mathbf A, \mathbf T, k) = \sum_{i=1}^k \mathbf A \times \mathbf T^i $$

进行分治处理 (以下忽略 $\frac 1k$ 的系数).

$$ \begin{aligned} &f(\mathbf A, \mathbf T, 2m)\\ ={} & \mathbf A\times \mathbf T + (\mathbf A \times \mathbf T^2) + \dots + (\mathbf A \times \mathbf T ^{2m}) \\ ={} & f(\mathbf A\mathbf T+\mathbf A\mathbf T^2, \mathbf T^2, m) \end{aligned} $$

对于 $k$ 为奇数的情况：

$$ \begin{aligned} &f(\mathbf A, \mathbf T, k)\\ ={}& \mathbf A+f(\mathbf A \mathbf T, \mathbf T, k-1) \end{aligned} $$

于是我们用 $\mathcal O(n\log k)$ 的时间解决了问题. 当然亦可以建出内向基环树.

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int n; ll k; cin >> n >> k;
    const int MOD = 998244353;
    using mint = modint<MOD>;
    using vm = vector<mint>;
    vi tmp(n), T(n); rds(T), rds(tmp);
    vm A(n);
    transform(allu(T), T.begin(), [&](int x) { return x-1; });
    transform(allu(tmp), A.begin(), [&](ll x) { return x%MOD; });
    const auto add = [&](const vm& lhs, const vm& rhs) {
        vm res(n);
        for (int i=0;i<n;++i) res[i] = lhs[i]+rhs[i];
        return res;
    };
    const auto mul = [&](const vm& lhs, const vi& to) {
        vm res(n);
        for (int i=0;i<n;++i) res[to[i]] += lhs[i];
        return res;
    };
    const auto trans = [&](const vi& v) {
        vi res(n);
        for (int i=0;i<n;++i) res[i] = v[v[i]];
        return res;
    };
    vm res(n);
    ll tmp_k = k%MOD;
    A = mul(A, T);
    while (k) {
        if (k&1) res = add(res, A), A = mul(A, T);
        A = add(A, mul(A, T));
        T = trans(T);
        k /= 2;
    }
    mint inv = 1/mint(tmp_k);
    for (int i=0;i<n;++i) cout << res[i]*inv << " \n"[i == n-1];
}

/ 相处的时间 你我已命运相连 /

/ 音乐频率凋谢 默契超越一切 /

/ 已记不清有多少个深夜你独自伏案桌前 /

/ 彻夜无眠 只为让我更耀眼 /

—— Kide - 星愿 ft. 星尘

Desc.

Link.

定义好串为一个或多个偶回文串拼接的结果. 给出一个字符串, 求其为好串的子串数.

Sol.

考试的时候犯病了, 求 $f_i$ 居然没有想到任何字符串算法, 而去连边写成了图论题... 有点离谱. 🤔

容易想到一个 DP, 设 $f_i$ 表示在 $i$ 结尾的极短偶回文串的长度, $g_i$ 表示在 $i$ 结尾的好串数量, 有 $g$ 的转移:

$$ g_i = g_{i-f_i}+1 $$

若 $f_i$ 不存在则为 $0$. 接下来考虑怎么求 $f_i$.

我们先求出 $rad_i$ 表示以间隔 $i$ 为中心的回文串长度, 这个可以用各种姿势求, 比如二分 & 哈希, PAM, Manacher etc. 然后发现 $f_i$ 可以用一个 $rad_j$ 来更新, 其中 $j < i, j+rad_j \geqslant i$. 我们肯定希望 $i$ 和 $j$ 靠得越近越好. 于是倒着扫描, 用并查集维护连续段, 以 $rad_i$ 更新连续段. 这个有点没说清楚, 具体可以看代码, 代码应该会更好理解.

void solve() {
    int n; string tmp, s; cin >> n >> tmp;
    for (int i=0;i<n;++i) s.pb(tmp[i]), s.pb('|');
    s.pop_back();
    const int m = 2*n-1;
    const ull BASE = 1331;
    vector<ull> pw(m);
    vector hs(2, vector<ull>(m+1));
    pw[0] = 1;
    for (int i=1;i<m;++i) pw[i] = pw[i-1]*BASE;
    for (int i=0;i<m;++i) hs[0][i+1] = hs[0][i]*BASE+s[i]-'a'+1;
    for (int i=m-1;i>=0;--i) hs[1][i] = hs[1][i+1]*BASE+s[i]-'a'+1;
    const auto getHash = [&](int l, int r, int idx) {
        if (idx == 0) return hs[0][r]-hs[0][l]*pw[r-l];
        return hs[1][l]-hs[1][r]*pw[r-l];
    };
    vi rad(m);
    for (int i=0;i<m;++i) {
        int l = 0, r = min(i, m-i-1), res = 0;
        while (l <= r) {
            int mid = (l+r)/2;
            if (getHash(i-mid, i, 0) == getHash(i+1, i+mid+1, 1)) l = mid+1, res = mid;
            else r = mid-1;
        }
        rad[i] = res;
    }
    vi fa(m);
    iota(allu(fa), 0);
    const auto find = [&](int u) {
        while (u != fa[u]) u = fa[u] = fa[fa[u]];
        return u;
    };
    vi f(n);
    for (int i=m-2;i>=0;i-=2) {
        for (int j;(j=find(i+rad[i]))>=i;) {
            if (j%2 == 0) f[j/2] = (j-i+1)/2;
            fa[j] = j-1;
        }
    }
    vll g(n);
    for (int i=0;i<n;++i)
        if (f[i]) {
            if (i/2 >= f[i]) g[i] = g[i-2*f[i]]+1;
            else g[i] = 1;
        }
    cout << accumulate(allu(g), 0ll) << "\n";
}

/ 光与影　是否不该在这一刻相逢 /

/ 而你和我从来谁也不是谁的附庸 /

/ 我放逐自己残缺的魂魄 /

/ 在镜子背面那一国 /

/ 一路上从没有挽留过 /

/ 那些徒劳奔波　却不曾完整的我 /

—— Kide - 零和 Zero-Sum ft. Minus

今天和重庆市其他学校一起来到一中打了一场友谊赛兼 CSP 模拟赛, 考得并不怎么样, 就当作联赛来写写总结.

进入教学楼后扎在人堆里的窒息感还真是联赛的感觉. 密码下发后顺序开题, 感觉也是联赛的风格. 我真不太会写 T1 这种题, 搭 Next.js 博客用 AST module 给惯的. 写了一个小时还在挂, 就先放了.

T2 的贡献看起来没有什么性质. 看到 $\mathcal O(3^n)$ 给了 80pts, 直接放弃思考写了二十多分钟就去看 T3 了.

T3 T4 都没留太多时间, 毕竟我 T1 还放在那里的. 先把朴素分都打了, 然后想了下 T3 的乱搞. 直接改直径上的最大值应该过不了, 那就把所有可能成为直径的路径扣出来然后挨个检查. 大样例过了就没管了.

然后回到 T1, 表达树依然在挂. 最后只剩 30min 的时候决定摆烂打暴力了. 打完后检查了下, 在桌子上趴了会儿, 缓了缓酸胀的眼睛.

发成绩后一看, T3 居然过了, 其他题倒是没挂. 全是暴力怎么挂. $60+80+100+40=280$.

本次考试最贻笑大方的部分就是 T1了, 成为了排名正着数第一位没过 T1 的 🤡. 希望联赛不会出现这种问题, 这种比较贴近实际的题, 写代码前先把框架组好, 就像写这个博客的源码一样. 同时希望最后一个月里心态能够更稳健吧, 最近老是被机房里面一些莫名其妙的事情惹得心烦, 这样不好. 无论学 OI 还是作为一个人而活着, 心态都是最重要的. 凭我浅薄的认知, 同我一样喜欢星尘的老前辈毛彦升心态就比较稳, 应当多向先辈学习!

/ 你盛开于那盛夏的污浊 /

/ 我流连于那温柔的疼痛 /

/ 燃烧坠落的那星火 /

/ 如梦一闪而过 /

—— Zeno - 涟漪 ft. 星尘

date: '2023-10-16'
title: 'Solution Set -「LOC 4326」'

Link.

A. 路径 (path)

设 $f_u$ 表示到 $u$ 时凑出的路径节点个数. 以拓扑序转移即可.

B. 异或 (xor)

先差分, 将区间操作转化为双点 (或单点) 操作. 把双点操作抽象成连边, 每个连通块的步数下界是连通块大小减一, 上界是连通块大小.

结论: 取得下界当且仅当连通块异或和为零.

证明:

• 必要性: 因为是一个连通块, 又只进行了大小减一次操作, 因此每次操作都是双点. 因此连通块异或和不变, 因此连通块异或和是 $0$;
• 充分性: 当连通块异或和为 $0$, 设最后一个元素为 $x$, 则前面元素的异或和也为 $x$, 每次操作选择一个未被选择过的非最后一个元素的元素, 令其与最后一个元素均异或其, 操作次数为连通块大小减一.

答案即为 $n$ 减去最大的异或和为零的子序列划分数. 状压即可.

C. 距离 (distance)

我甚至没学过点分树...

考虑单点. 建出点分树, 令 $d(x, y)$ 表示原树上 $x, y$ 的距离, $f(p)$ 表示目前已经插入点集且在点分树中 $p$ 的子树里的点中, 距离 $p$ 最近的点. 那么对于一个询问 $a$, 枚举 $a$ 和 $a$ 在点分树上的祖先 $p$, 答案就是 $d(a, p) + \min(f(p))$, 注意我们不需要排除 $a$ 本身在的这棵子树, 因为 $p$ 是 $a$ 和 $x$ 的 LCA 的祖先, 若 $x$ 和 $a$ 在 $p$ 的同一棵子树里, 答案一定更劣.

再考虑点对. 对于一个询问 $(a, b)$, 把路径拆成 $x \rightarrow p \rightarrow a$ 和 $y \rightarrow q \rightarrow b$. 设 $f(p, q)$ 表示与 $f(p)$ 类似的含义, 预处理出来我们就可以回答询问了. 但是 $\mathcal O(n^2)$ 的空间并不能承受, 于是把询问挂载在 $a$ 到根的路径上, 求 $f_p(q)$ 即可.

说着简单, 代码还是有点难度的, 尤其我对点分树完全不熟悉...

D. 花之舞 (dance)

不会.

/ 即使我们分隔　在遥远的两端 /

/ 我会始终凝望　你存在的方向 /

/ 很感谢你曾经赋予给我的最特殊的意义 /

/ 为我描画翅膀　去向蔚蓝之上 /

/ 闪烁最动人的星光 /

—— Evalia - 星辰 ft. 星尘