1.14 模拟赛

A 环游

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

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

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

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

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

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

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

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

B 电梯

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

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

由于每一个 AiA_i 都必然导致 11 的个数增加 xx 中的 11 的个数,所以我们知道构造的 xx 中必然有 hn\frac h n11 ,若不整除显然无解。

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

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

考虑当前我们需要计算有多少长度为 HHbitset 满足 11 个数为 nn ,那么我们有两种操作:

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

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

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

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

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

C 计数

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

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

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

其中 w[j]w[j](xi)=j\binom x i = jii 的数量,xxnnpp 进制在当前位下的值。

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

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

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

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

这个做的就是:

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

也就是一个和卷积了。

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

\