在文章《NOIP 2025 HA 迷惑行为大赏》发表评论：

神入 _ANIG_ 上厕所忘带准考证。

没有思考难度的做法。 一个暴力是枚举 $i$，求包含 $i$ 的答案，枚举 $r$，合法的 $l$ 是一个区间。直接 ST 表即可 $O(1)$ 查询。 注意到 $i$ 关于 $r$ 有决策单调性。于是做完了，直接朴素分治是 $O(qn\log n)$，用 SMAWK 可以做到 $O(qn)$。

[传送门](https://www.luogu.com.cn/problem/CF1740H) 首先每个点的权值不会超过 $O(\log n)$。考虑造出来权值为 $i$ 的点需要几个点，设其为 $f_i$，可以得到转移式：$f_i=\sum\limits_{j=0}^{i-1}f_j$，$f$ 显然是指数级增长的。…

[传送门](https://qoj.ac/contest/2578/problem/14583) 首先这个题看起来很难直接贪心，难以观察出来任何结论，所以唯一可能的思路是网络流。这个形式很容易让人联想到最小割。 但是建模似乎非常困难。常见的模型都不太能适用。 而这个题要把每个点划分到三个集合之一，这种形式比较符合最小割…

难绷做法。 首先考虑如何判定一个方案是否合法。看看我们的操作不能改变什么，注意到如果 $a$ 中存在顺序对，则这个顺序对一定不能变成逆序对。 于是合理猜测充要条件就是 $a$ 中所有顺序对都保留。 考虑如何对着这个做。所有顺序对保留，相当于对于所有 $i using namespace std; const int N…

魔怔做法。 首先题目给你的这个图看着很神秘，于是肯定要先分析一下他给你的这个性质有啥用。 观察一下图可以发现意思就是对于每个点，连向这个点的点中不存在三元环。 三元环不能给我们太多信息。但这个图是竞赛图，于是合理猜测没有三元环的竞赛图一定是 DAG。 证明是容易的，考虑归纳证明竞赛图 $n$ 个点的环的导出子图一定存在…

神秘做法。 询问次数和序列长度都是 $1000$，考虑逐位确定。 可以发现前几位是很好确定的，只需要先造一条链，等走到第一个没确定的点就分叉，然后连自环。 这样就可以根据最终去了哪个分支得到这一位是什么。 但是只有 $102$ 个点，在确定后面的点时，我们做到用一个很小的图让一个很长的字符串精准走到一个点，并且要求这个…

写的侧重点在于为什么能这样 dp，建议配合其他题解食用。 首先第一眼能想到的状态是 $f_{l,r,a,b}$ 表示横坐标 $[l,r]$，纵坐标 $[a,b]$ 的矩形划分得到的序列数量。 直接算会重复，一个经典的套路是构造出操作序列和最终结果序列的双射，使得最终序列可以被唯一操作出来。 也就是给操作加一些限制，使得…

首先转化成这个问题：一个长度为 $\sum l_i$ 的线段上，初始每隔 $l_i$ 的位置选了一个点，每次操作在线段上随机选一个点，问相邻两个点距离都不超过 $k$ 的期望时间。 考虑 $n=1$ 怎么做。首先根据经典技巧：期望时间等于到达每个非终止状态的概率和。考虑求出到达每个非终止状态的概率和。 由于我们是在实数…

前置知识：普通生成函数。 首先问题相当于对于每个无标号有根树，求其出现的概率 $k$ 次方之和。 也就是： $$=\sum\limits_{a\in A}p_a^k$$ $$=\sum\limits_{a\in A}\left(\frac {g_a}{(n-1)!}\right)^k$$ $$=\frac{1}{(n-…

[传送门](https://www.luogu.com.cn/problem/CF1119H) 首先一个显然的做法是直接 FWT。 设 $F_{i,j}=FWT(f_i)_j$，其中 $f_i$ 是只有 $a_i,b_i,c_i$ 三项分别是 $x,y,z$ 的数组。设 $g_i=\prod\limits_{j=1}^…

本文介绍的是针对于 SAM 上的 DAG 链剖分。 前置知识：SAM，树链剖分。 众所周知，我们可以快速在 SAM 上找到一个字符串，并且可以用一个节点在 parent 树上到根节点的路径表示一个字符串的所有后缀，但是无法很方便地表示一个字符串的所有前缀。 考虑一个字符串的所有前缀在 SAM 上对应的点是什么。 由于在…

[题目链接](https://qoj.ac/problem/6197) ## 题意： 定义两个长度均为 $m$ 的字符串 $A,B$ 同构，当且仅当存在一个排列 $p$，使得对于任意的 $1\le i\le m$，$p_{A_i}=B_i$。 给定 $n$ 个字符集为 $k$ 的字符串 $S_1,S_2,\dots,S…

在讨论《关于什么数据范围可用 set》回复：

感觉 1e6 级别的运算 set 已经很慢了，1e6 以上最好别用，除非这个题是裸的set

[传送门](https://www.luogu.com.cn/problem/CF1919H) 题意：给定整数 $n$，有一棵大小为 $n$ 的树，你需要通过以下两种询问问出树的形态： 1. 给每条边赋 $[1,10^9]$ 的权，求带权直径。 2. 给定两个编号，回答这两条边的距离。 两种操作都不能超过 $n$ 次。…

题意大概是根据冲突次数问出来哈希模数。 实际上，本题中无需知道冲突次数，只需知道是否冲突。 考虑集合 $S$ 冲突的充要条件，可以发现就是看是否存在两个数 $x\in S,y\in S$，且 $x\equiv y\pmod n$。 也就是是否存在两个数 $x\in S,y\in S$，且 $n|x-y$。 如果我们能构…

首先可以发现人类可以轻松解决这个问题，但是完全不知道怎么写。 解的数量显然很多，看上去你随便构造一个都是对的。 可以发现，如果只有两个颜色，似乎更好构造一点，于是考虑先确定一个颜色。 要让剩余两个颜色很可能合法，则第一个颜色构成的图形要尽量规则。 把第一个颜色平移到右下角。可以感受到填成长方形似乎比较优。 于是考虑划定…

在讨论《求问不知道什么题》回复：

@[zzy_zzy](luogu://user/760776) 感觉不太行。也可以后缀排序+二分

在讨论《求问不知道什么题》回复：

SAM 板子

在讨论《求教二分，萌新刚学完语法和入门算法》回复：

@[EricWan](luogu://user/377873) https://qoj.ac/problem/2211 做完这个题你 wqs 二分可以毕业了。

首先状态是简单的： $f_x$ 表示当前考虑所有右端点不超过 $x$ 的区间，且存在一个类型为 $3$ 的右端点为 $x$ 的区间被选了。 从左往右扫，动态维护前两类区间的贡献。 设当前扫到 $i$，把 $f_x$ 表示为最后一个被选的类型为 $3$ 的区间右端点为 $x$，且考虑了 $x+1$ 到 $i$ 之间的所有…

## 简介 可以解决的问题： 给定两个长度为 $n$ 的数列 $A,B$，求数列 $C$，满足 $C_{k}=\sum\limits_{i\oplus j=k}A_iB_j$（本文的 $n$ 均代表数列**总长度**）。 其中，$\oplus$ 是一种位运算。 众所周知，FFT 通过将多项式系数转点值，然后通过点值相乘…

在讨论《洛谷学员进省队 55 人》回复：

St××××wr 是我们省的 A 队，是去年初三，今年高一，我们机房的，跟我们一个学校，很厉害啊！

[传送门](https://www.luogu.com.cn/problem/P11948) 考虑树的情况。 首先问题可以转化成找到一条路径，把这条路径染成单调递增，其余点染成距离最近的路径上的点。 要求不同颜色点对最小，就是要求同色连通块大小平方和最大。 假如我们钦定了一个端点，则另一个端点是可以简单 dp 求出来的…

在文章《DGF 不存在了：Dirichlet 卷积的 n(loglogn)^2 做法》发表评论：

OOrz

背景：本人在模拟赛中遇到了形如 $\sum\limits_{i=1}^C\binom{A-i}{B}i$ 的式子，本以为不可做，后来发现这个东西可以 $O(1)$ 求，由于网上没见过这类式子的求法，所以小小总结了一下。 前置知识： $$\binom{n}{m}=\binom{n+1}{m+1}-\binom{n}{m+…

说的比较简略，不保证全对。 # 基本运算 ## 二维向量 ### 加减 $$(x_1,y_1)+(x_2,y_2)=(x_1+y_1,x_2+y_2)$$ $$(x_1,y_1)-(x_2,y_2)=(x_1-y_1,x_2-y_2)$$ 对于平面上的两个点 $A(x_1,y_1),B(x_2,y_2)$，则向量 $\…

在文章《题解：P11629 [WC2025] Nim 游戏（暂无数据）》发表评论：

赛时并非通过2人，而是4人（有两个100+100+40）

# DAY -2 狼人杀！ # DAY -1 打牌！ # DAY 0 摆！ # DAY 1 开 T1，会了，写 T1，过 T1。 开 T2，不会。 开 T3，先写了 40pts 暴力。 开 T2，会了，写 T2，过 T2。 比赛结束了。 我们有一位选手场切了 WC2025 最难题，他一定获得了 au 吧！ # DAY…

坐了 6h 高铁到了绍兴，在高铁上用掉了 13G 流量。 # Day1 进场，发现没带笔。 蚌埠住了，不管了，尝试使用画图软件，但是并不知道 linux 有什么画图软件。 随便找了一个，发现不好用。 试机题看了一下，发现不会做。 于是不管了，写了个拍子，写了个 NTT 板子。 快进到比赛开始。 一眼注意到 T3 题目名…