1.14 模拟赛 | yijan's Blog

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$ ，所以我们可以每一位都保证它在上界里面。于是现在要做的就是：

dp[k] = \sum_{i\times j = k} dp[i]w[j]

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

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

dp'[i] = dp[\omega^i]

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

dp'[k] = \sum_{\omega^{i+j} = \omega^k} dp[i]w[j]

这个做的就是：

dp'[k] = \sum_{i+j=k} dp'[i]w'[j]

也就是一个和卷积了。

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