1.14 模拟赛

A 环游

看起来是毒瘤题,其实不然。

我们设首都是 $a$ ,秘密都市是 $b$ ,新建城市是 $c$ ,我们需要找到的就是一条 $a \to c \to b \to a$ 的路径,且保证 $a \to b$ 有至少三条点不相交路径。

现在假装我们已经拿出了三条 $a \to b$ 的路径。我们考虑先尝试找到一条 $a \to c$ 的路径,然后找出它最后一次经过 $a \to b$ 的三条路径之中的任意一条的某个点 $v$ 。然后我们可以把 $a \to c$ 变成 $a \to v \to c$ ,这样就只会经过一条 $a \to b$ 的路径。再尝试找出一条 $c \to b$ 的路径,找到它第一次经过 $a \to b$ 的某条路径的位置 $u$ ,然后可以把它变成 $c \to u \to b$ ,如果不存在这个位置当然更好。这样我们一共只花费了两条 $a \to b$ 的路径就得到了一条 $a \to c \to b$ 的路径,可以再用一条来返回 $a$ 。

因此可以发现,这个东西有解的充要条件其实就是 $c \to a , c \to b$ 有两条点不相交的路径。

一种非常好写的实现是,先找出三条 $a \to b$ 的点不相交路径,枚举一条作为 $b \to a$ 使用的路径,然后看看能否再不经过这条路径的时候找到 $c \to a , c \to b$ 的点不相交路径。如果可以,显然得到了一个答案,否则枚举另一个即可。

如果三个路径都无法找到答案,显然意味着 $c \to a , c \to b$ 无法找到两条点不相交路径。输出无解即可。

由于这里网络流只需要流 $3$ 的流量,我们可以暴力找流。

复杂度 $O(n + m)$ 。

B 电梯

读不懂题。佳老师教我的题意:

数有多少 $A_1<A_2<\dots<A_n$ , $A_1 = 0$ ,使得存在长度为 $H$ 的 bitset $x$ 满足 x<<A1,x<<A2,...,x<<An 的并为全集且两两无交。

由于每一个 $A_i$ 都必然导致 $1$ 的个数增加 $x$ 中的 $1$ 的个数,所以我们知道构造的 $x$ 中必然有 $\frac h n$ 个 $1$ ,若不整除显然无解。

然后我们知道如果 $A_1 < A_2 < \cdots < A_n$ ,那么一组 $A_1,A_2, \dots , A_n$ 一定对应唯一一组 $x$ 。对于一个 $x$ ,我们只需要暴力尝试一下 x<<1,x<<2,...,x<<h 哪些是无交的即可。

我们考虑如何统计满足这个条件的 bitset 的个数。

考虑当前我们需要计算有多少长度为 $H$ 的 bitset 满足 $1$ 个数为 $n$ ,那么我们有两种操作:

  • 把整个序列分成很多个块,然后只在第一个块里面递归做,最后把第一个块通过一些 $A_i$ 左移填满整个序列。
  • 把整个序列分成很多个块,然后每个块都放相同的数。然后就不需要新增 $A_i$ 。

但是直接递归下去做肯定是不对的,因为如果我们连续两次进行第一种分块,其实会被直接分一次第一种给算到这种方案,这样会导致算重。所以说我们一定是间隔着分的:先按照第一种方案分,然后第二种,然后第一种……

所以我们计算 $H,n$ 的时候可以直接枚举两次,先枚举一次第一种再枚举一次第二种。两种都不能分自己。

然后还需要注意的是刚开始进行分块的时候是可以分自己的,因为第一次分块第一种第二种都可以。

然后这题 Subtask 导致没判 1 1 直接爆 $20$ 分。。。。其他点都是对的。

C 计数

考虑 Lucas 定理。那么要算的就是 $n,m$ 在 $p$ 进制下每一位分别做组合数并乘起来等于 $x$ 的方案数。

我们可以先把 $n$ 通过高精度除法,取模化成 $p$ 进制。然后考虑进行一个数位 $dp$ ,设 $dp[i]$ 表示当前 $\bmod p$ 乘积为 $i$ 的方案数量。这个题里面是否卡着上界是不重要的,因为就算超出了上界,贡献也一定是 $0$ ,所以我们可以每一位都保证它在上界里面。于是现在要做的就是:

其中 $w[j]$ 为 $\binom x i = j$ 的 $i$ 的数量,$x$ 是 $n$ 的 $p$ 进制在当前位下的值。

这个东西就是一个套路了,我们先对 $dp$ 进行一个变换,使得

其中 $\omega$ 是原根,我们知道只要读入的是质数就一定存在原根。于是我们对 $w$ 也进行这个操作,就变成了

这个做的就是:

也就是一个和卷积了。

于是转移的复杂度就是 $O(p\log p)$ ,总复杂度就是 $O(p \log_pn \log p)$ 。

文章作者: yijan
文章链接: https://yijan.co/2021/02/13/114-mo-ni-sai/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog