远方有一堆篝火,在为久候之人燃烧。
[ARC083F] Collecting Balls
总共有 $2n$ 个球和 $2n$ 个机器人,所以每个机器人必须拿一个球。考虑一个球 $(x_i,y_i)$,它要么被第 $x$ 个 $A$ 类机器人领走,要么被第 $y$ 个 $B$ 类机器人领走。
于是我们可以把问题放到图上来考虑:
- 将 $A$ 类机器人编号为 $1\sim n$,将 $B$ 类机器人编号为 $n+1\sim 2n$,所以对于每一个球 $(x_i,y_i)$,我们将第 $x$ 个 $A$ 类机器人和第 $y$ 个 $B$ 类机器人连边,即将 $x$ 和 $n+y$ 连边。
由于每个球要被一个机器人认领,所以问题变为了:将 $2n$ 条边定向,使得每个点只有一条入边。不难发现满足条件的图是一个内向基环树森林。
定向很显然,环外的节点只有一种选择,而对于环上的节点有顺时针和逆时针两种选择,暴力枚举这两种情况就可以了。
现在每个机器人已经认领了一个球,目前就要确定有多少种排列方式就行了。
但是题目中要求机器人只能拿最近的球,所以在 $A$ 类机器人 $(x,0)$ 去拿 $(x,y)$ 的球时,需要 $B$ 类机器人将 $(x,t),t\in [1,y)$ 上的球拿完,所以这些 $B$ 类机器人就是这个 $A$ 类机器人的先前条件,$A$ 类对于 $B$ 类亦然。将这些条件连边,可以得到另一个图。
由于每个 $B$ 类只可能是一个 $A$ 类机器人的先前条件($A$ 类对于 $B$ 类也是一样),所以每个点只有一条出边,而且不难发现不会有环,所以这个图是一个内向树森林。
所以排列数就是求这个内向树森林的拓扑序个数,由于每个节点在它的子树内所有节点中第一个出现的概率为 $\dfrac{1}{siz_x}$,而且每个节点独立,所以可以得到拓扑序个数为($S$ 为森林点集)
$$ \frac{|S|!}{\prod_{x\in S}siz_x} $$最后将每颗内向基环树的两种顺逆方式的情况相加,得到每颗内向基环树的方案,答案就是将所有内向基环树的方案相乘并且乘上一个组合数即可。
[ARC084F] XorShift
将所有数转成二进制形式,然后每一位对应多项式的一项,多项式模数为 $2$。
乘以 $2$ 相当于对多项式乘以 $x$;异或相当于对多项式做模意义下的减法。
假设我们现在有两个多项式 $P,Q$,每次取最高位较小的多项式,然后不断乘以 $x$ 使得两个多项式的最高位齐平,再相减,利用这种类似辗转相减的操作,我们能得到 $H=\gcd(P,Q)$。
上边这个操作是 $O(\log^2 V)$ 的,不管怎样,我们利用 $P,Q$ 得到的多项式一定能整除 $H$,而有了 $H$,我们就可以得到任何能被 $H$ 整除的多项式,也就是用 $H$ 代替了 $P,Q$。
于是我们设 $G=\gcd{A_1,A_2,\cdots,A_n}$,那么接下来要求的就是用多少个能被 $G$ 整除的多项式小于 $X$。
假设这个多项式为 $P=QG$,由于 $P$ 的最高位只与 $Q$ 的最高位和 $G$ 的最高位有关,所以简单的分类讨论即可。
多项式用 bitset 维护,总复杂度 $O(\frac{n\log^2 V}{\omega})$