这个 $A_i\in \{ -1,1\}$ 太逊了，我们看看丢掉这个条件能不能做。 考虑使用差分数组刻画限制： $$ \begin{align*} &\sum_{i=1}^n A_i \sum_{j=1}^i c_i=0\\ &\sum_{i=1}^n c_i \sum_{j=i+1}^n A_i=0 \end{ali…

考虑拆分一次游走过程：我们定义“一次操作”为在 $u$ 处进行一次判定后发现没有结束，然后从 $u$ 走到 $v$。 设当前状态下 $u$ 的出度为 $d$，则该次操作的贡献为 $\dfrac {(1-p_u)} d$。 以下 dp 过程中使用“概率”一词似乎并不是非常恰当，我们认为一条路径的“权值”为每次操作的贡献的…

直接容斥，用总数量减去不合法的数量。 考虑将题目转化为一个格路计数问题：$(i,a_i)$ 位置禁止经过，判定是否存在一条从 $(0,b)$ 出发，每次从 $(x,y)$ 走到 $(x+1,y\plusmn 1)$ 的位置能否走 $n$ 步。 首先对于判定问题，我们显然会优先向 $(x+1,y+1)$ 走，并且一旦碰到…

在文章《日记 - 019》发表评论：

加油

有趣的结论题。 先考虑树上问题。此时“紧密”的点集其实就是非平凡菊花图。 手玩一些情况，我们注意到一个事实： > Lamma 1：对于一棵 $n\ge 2$ 的树，一定存在至少一种划分方式。 > > 证明：考虑归纳，设我们已经证明了 $2\le n\le k$ 时均存在拆分方式，现在证明 $n=k+1$ 时存在拆分。…

dyc 告诉我们，写游记要用一些看上去很牛逼的话作为开头。 那就从某个知名 OI 网站上贺一个下来吧。 很好，就这个。  - - - #### Day -333 具体是什么时候忘记了，WC 前发…

写树剖时想到一个很有趣的问题。 考虑使用树剖维护链上所有节点权值 $+x$ 的操作。如果我们在树剖时随机设一个儿子节点为重儿子，不保证树形态和操作随机，那么期望的时间复杂度是多少？ dalao 们能不能顺便给个这种做法的复杂度证明 /kel

我嘞个容斥仙人啊！ 首先这个 $2^{\mathrm{cnt}}$ 就很奇妙，考虑赋予其一个组合意义：每个环要么选上，要么不选。注意到这里可以顺便容斥掉出现偶环的情况。具体地，选出一个偶环乘上 $-1$，选出一个奇环乘上 $1$，则存在奇环的图都会被我们容斥掉。 假设我们选出的环上的点的集合为 $S$，显然 $1\in…

在讨论《洛谷举报专区》回复：

举报 @[China_qwq](/user/1628162) 抄袭题解。 这个号从 12-27 号开始就以 两分钟/题 的速率做黑题，目前共写了 300 余道黑题。

看了下大佬们的题解，我不觉得这个把 $\texttt{01}$ 看成不等号的等价转换是人类能想出来的东西，来一个我自己的思考过程吧。 本题还有一个思考方向：保留 $\texttt{?}$，去掉 $\texttt{1}$，通过容斥算贡献。 - - - 直接考虑题目中的过程，为了不算重，考虑加一个限制：每次删掉的数要满足…

好题，补一下题解。 注意到对于 $k=1$ 的情况不弱于[最小树形图](https://www.luogu.com.cn/problem/P4716)的板子。 > 回顾一下朱刘算法的过程：我们维护了一个内向树森林，每次取出一个没有出度的根节点 $u$，找到它的最小出边 $v$，则有两种情况： > > 1. $u$ 和…

从 CF1943D2 的 [这篇题解](https://www.luogu.com.cn/article/qtxffhtf) 的同类题里找到的东西，还挺有意思的。 > 给定序列 $w$，定义一个长度为 $n$ 的序列 $a$ 的权值为 $\prod_{i=1}^{n-2} w_{\max(a_i,a_{i+1},a_{…

在讨论《站外题求卡空间》回复：

@[dyc2022](/user/504093) 对于长度 $\ge B$ 的环，可以加一个小优化： 先把前缀和预处理出来。 简洁起见，把每个询问拆分成 $(x,r)$ 的二元组，表示当前对这个环旋转了 $x$ 次之后，有一个 $[1,r]$ 的询问。 如果所有二元组都按照 $r$ 进行排序，那就可以直接用双指针找到位…

在讨论《求树状数组毒瘤题》回复：

@[YangYiCheng123](/user/1497170) P4528

在讨论《能帮帮我吗？9个TLE》回复：

@[qianhy_cool](/user/1462752) 代码的时间复杂度过高，建议学习本题的相关算法

在讨论《关于杀和决斗的顺序》回复：

@[fish_love_cat](/user/754021) 取决于你的决斗和杀的顺序。 因为决斗和杀都能用，所以根据题目描述，如果决斗在左边先用决斗，否则用杀

在讨论《关于fhq随机merge的复杂度?》回复：

因为你在合并两颗不同大小的子树时，u 的rk更大的概率其实不等于 1/2

在讨论《关于fhq随机merge的复杂度?》回复：

@[shenzirui](/user/486056) fhq 的随机函数需要改为 $\frac {siz_u} {siz_u+siz_v}$ 的概率让u作为根

在讨论《新手P1830轰炸三指针越界求解》回复：

此外，不建议在函数内部定义数组，比较大的数组应该定义在函数外。并且数组长度最好不要由 **输入的数字** 确定

在讨论《新手P1830轰炸三指针越界求解》回复：

@[Zhangzehao00118](/user/1319117) `a[n]` 的下标范围是 $[0,n-1)$，所以当你定义了一个 `a[n]` 时访问 a[n] 就会数组越界

在讨论《求昨天 G 相似的题》回复：

AT_abc288_h

在讨论《本题已添加 hack 数据并撤下错误题解》回复：

qp

在讨论《听说洛谷大佬多》回复：

解决 jcer

在讨论《米欧还能够……》回复：

因为你 g(g(x)) 可能是 2

在讨论《米欧还能够……》回复：

即改成 ```cpp if(k%2==1){ cout<<!g(g(x))<<endl; }else{ cout<<!!g(g(x))<<endl; } ```

在讨论《米欧还能够……》回复：

@[lucy2012](/user/1252442) 在 k%2==1 的else部分的g函数前面加两个感叹号

在讨论《米欧还能够……》回复：

@[lucy2012](/user/1252442) g函数中 x=0 没有特判

在讨论《建议降紫》回复：

附议

在讨论《站外题求助》回复：

@[rnfmabj5114](/user/917683) ~~暴力打表可知~~ 你考虑欧拉函数的计算方法： $$\varphi(n)=n\prod_{p|n} \frac {p-1} p$$ 所以 $\varphi(n)|n \Leftrightarrow \prod_{p|n}\frac p {p-1}\in \N^…

在讨论《站外题求助》回复：

假设 $d$ 中含有 $a$ 个 $2$ 和 $b$ 个 $3$，则 $a,b\le k\log V$，每个物品会贡献若干 $2$ 和 $3$，这是一个二维背包