0103abc 的网站

请先阅读 D1 题解。 考虑利用上面的两个性质解题，使用二分解决这个问题。对于给定的左端点区间范围 $[l,r]$，找出中点位置 $mid=\frac{l+r}2$，两次询问出 $\text{MEX}(l,n)$ 和 $\text{MEX}(1,r)$ 的值，设两个值分别为 $suf$ 和...

通过作差可以发现答案是一个 $k+1$ 次多项式的形式，因此想到 Lagrange 插值。将 $x_i=i$（$0\le i\le n$）带入，有： \begin{aligned} &\sum\limits{i=0}^nyi\prod\limits_{j\neq...

根据 CF2163D1 的结论可知，对于一个左端点，只有右端点最大的区间是有用的，因此只需要保留最多 $n$ 个区间。 考虑对询问区间和给定的区间分别排序然后双指针扫描，对于一个询问区间，将右端点在其右端点左侧的覆盖区间加入到线段树中，则此时询问区间 $[ql,qr]$ 合法的充要条件是：...

前置题目：P4839 P 哥的桶。 首先知道线性基是可以合并的，且具有交换律。因此容易想到线段树维护区间线性基，但是这样无法支持区间异或的操作。此时容易想到分块处理，但是这样时间复杂度变为 $O(n\sqrt n\omega^2)$ 其中 $\omega$ 为位数这里取...

挺有意思的题。注意到两个点 $u,v$ 相邻时，必然满足对于任意一个点 $x$，都有 $\text{dist}(u,v)=\text{dist}(u,x)\oplus\text{dist}(v,x)$。 然后随便咋做就都能过了（比如说随机一个排列 $p$ 然后按照 $p$...

严肃学习差分约束。 具体而言，对若干个不等关系可以考虑建图。假设不等关系形如 $xa-xb\le c$，那么从 $b$ 向 $a$ 连一条边权为 $c$ 的单向边。 同理，对于 $xa-xb\ge c$ 的不等关系，考虑对不等式两边同时乘 $-1$ 然后不等式变号，得到 $xb-xa\le...

感觉是挺套路的题，考虑相邻位置之间建边，若值为 $i$ 的两个位置分别出现在第 $x$ 列和第 $y$ 列，那么： 若两个位置出现在同一行，则必须换，在 $x,y$ 之间连一条权值为 $1$ 的双向边。 若两个位置不出现在同一行，那么必须相对不换，在 $x,y$ 之间连一条权值为 $0$ 的双向边。...

先考虑一条链的情况。此时有两类形态： $1$ 号结点是链的一个端点。 $1$ 号结点在链的中部。 第一类情况是简单的，显然任意两个点之间都有祖先关系，直接把所有点都单独划组，答案即为所有点的代价的和。 第二类情况就是合并两个链，链内所有元素...

这个比上个题简单的不是一点半点吧（） 根据第二类斯特林数的经典通项公式可知： $$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\frac{i^n(-1)^{m-i}}{i!(m-i)!}$$ 令...

题目要求的东西太别扭了（你猜为什么我 wa 了一发），这里改一下变量名的顺序： 给定 $n,k$，对 $i=0\ldots k$，求 $\begin{Bmatrix}i\\n\end{Bmatrix}$ 的值。 第二类斯特林数的生成函数形式是：...