分类 题解 下的文章

给定麻将的权值大小 n 和默认的 13 张手牌,求期望意义下的最小胡牌巡目数。

一道有意思的 DP 套 DP。发现如果我们可以知道 i 步后还未胡牌的方案数,就可以算出期望最小胡牌巡目数。

考虑一个判断牌是否可以胡的 DP:用 f[i][j][k][0/1] 表示对于权值 1 ~ i,预留了 j(i-1)iki,是否预留了一个对子的最大面子数。注意这样做是没法处理七对子的,但我们可以稍后特判。

显然,i 是多少与 DP 的转移没有关系,考虑建出一个自动机来维护转移。在自动机的节点上同时记录一下之前的牌可以凑出几个对子(注意不是预留)。显然一个节点是胡的当且仅当存在的对子数大于 7 或预留了一个对子且面子数大于等于 4。显然这个转移中会有大量重复节点,将他们压掉之后自动机上只有 2092 个点。

最后在自动机上 DP ,用 f[i][j][k] 表示当前枚举到权值为 i 的牌,到达自动机的 j 号点,其中自摸了 k 张牌的方案数。实现时可以滚动掉一维。

总时间复杂度 \mathcal O(n^2 \times K) 。其中 K = 2092

READ MORE

首先可以发现,最后的结果一定是所有点 [1, n)n 连边。对于给定的图,其中已经有若干条从 n 连到一些其他点的边,通过这些边可以将原来的图分裂成若干个区间。对于一个区间 [l, r] ,仅存在边 l \leftrightarrow nr \leftrightarrow n,对于所有 i \in (l, r) 不存在 i \leftrightarrow n。显然对于 r - l > 1 的情况,我们一定可以在 (l, r) 的范围内找到一个点 u,使得 l \leftrightarrow uu \leftrightarrow r,从而将这个区间分裂为两个更小的区间 [l, u][u, r]

显然每做一次树上操作,一定会多一个点与 n 连边,显然这样做是最优的。考虑如何统计方案数:相当于每棵子树的根节点一定要在选择其子树前被选择;考虑对于子树根节点的选择序列,首位一定是根节点,后面部分即将两棵子树的序列归并起来的值,即 \displaystyle \frac {(\operatorname{size}(lc) + \operatorname{size}(rc))!} {\operatorname{size}(lc)! \cdot \operatorname{size}(rc)!} 。最后的答案即若干棵子树合并起来的值。

考虑修改操作,我们依然可以在树上方便的维护。对于一次修改 (a, c) ,我们可以方便地求出 (b, d),然后根据 d 分类讨论。

READ MORE

要求维护一棵树,支持:

  • 给定 x, y, w,其中 w \in \{-1, 1\},将 xy 链上所有点权加上 w
  • 给定 x, y,查询 xy 的链上点权大于 0 的点的个数
  • 给定 x,查询 x 的子树内点权大于 0 的点的个数

n \leq 100000,时限 2s 。

READ MORE

被 mwh 嘲讽:「你会 SAM 吗,你不是什么题都写 SA 的吗」 于是自己想出来了这题

考虑根号分治,对于一组查询 (l, r, k) ,我们先将其拆成 (1, r, k) - (1, l - 1, k)

length[k] > \sqrt n 考虑这样的 k 不会超过 \sqrt n 个,对于每个都在 SAM 上暴力 DFS 统计出每个形如 (1, i, k), i \in [1, n] 的答案,时间复杂度 O(n \sqrt n)

length[k] \leq \sqrt n 考虑先把所有 (1, i, k) 按照 i 从小到大排序。ij 产生贡献当且仅当 i 在 SAM 上的结束节点时 j 在 SAM 上某个节点的祖先。考虑扫描线,每次插入一个串就将其子树增加 1 ,每查询一个串就暴力遍历在 SAM 上的每个点查询,由于串的长度 \leq \sqrt n ,所以单个询问最多查询 \sqrt n 次。

如果使用线段树状物来维护子树的修改,时间复杂度是 O(n \sqrt n \log n) 的。考虑到修改只有 O(n) 次而询问有 O(n \sqrt n) 次,可以考虑使用 O(\sqrt n) 修改,O(1) 查询的分块来解决。

READ MORE

对于两棵树 T_1, T_2,定义它们的交 T_1 \cap T_2 是它们的边集的交形成的森林,k(T_1 \cap T_2)表示这个森林的连通块个数,求下列三种问题之一:

  1. 给定 T_1, T_2,求 y^{k(T_1\cap T_2)}

  2. 给定 T_1,求 \sum_{T_2}y^{k(T_1\cap T_2)}

  3. 给定 n,求 \sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}

其中 n \leq 10^5 ,上面的 sum 是对所有 n^{n-2} 种可能的树求和。答案对 998244353 取模。

orzrqy

READ MORE

先看 n=1 的情况,考虑令 a = w_{1, 1} ,用 f_i 表示跳了 i 步的答案,则 f_i = a^i \binom n i

考虑

\begin{aligned} ans &= \sum_{i \bmod k=m} f_i = \sum_{i \bmod k=m} a^i \binom ni \\ &= \sum_{i=0}^n [k|i-m] a^i \binom ni \\ &= \sum_{i=0}^n \frac 1k \sum_{j=0}^{k-1} \omega_k^{j(i-m)} a^i \binom ni \\ &= \frac 1k \sum_{j=0}^{k-1} \omega^{-mj}_k \sum_{i=0}^n \binom ni (\omega^{j}_k a)^i 1^{n-i} \\ &= \frac 1k \sum_{i=0}^{k-1} \omega^{-mi}_k \left(\omega^i_k a + 1\right)^n \end{aligned}

考虑后面的 \displaystyle{\left(\omega^i_k a + 1\right)^n} 对于固定的 i 是相同的,可以与先处理出 i \in [0, k) 的值,设为 c(i)

前面的部分有个暴力的做法就是多项式多点求值出多项式 \displaystyle{\frac 1k \sum_{i=0}^{k-1} x^i c(i)}\omega_k^0, \omega_k^{-1}, \omega_k^{-2} ... \omega_k^{-k+1} 的值,复杂度 O(k \log^2 k),然而貌似被针对了过不去 ...

考虑一个优秀一点的做法,如何处理 \omega^{-mj}?毛爷爷论文中有个做法是把 ij 拆成 \frac {(i+j)^2} 2 - \frac {i^2} 2 - \frac {j^2} 2 ,然而此题中可能存在单位根没有二次剩余的情况。考虑把 ij 拆成 \binom {i+j} 2 - \binom i2 - \binom j2 ,那么原式可以化为

\begin{aligned} ans &= \frac 1k \sum_{i=0}^{k-1} \omega^{-mi}_k c(i) \\ &= \frac 1k \sum_{i=0}^{k-1} \omega^{\binom {i-m} 2 - \binom i2 - \binom {-m}2} _k c(i) \\ &= \frac {\omega^{- \binom {-m}2}} k \sum_{i=0}^{k-1} \omega^{\binom {i-m} 2}_k \left( \omega^{- \binom i2}_k c(i)\right) \\ \end{aligned}

显然是一个卷积的形式,那么卷积下即可,复杂度 O(k \log k)

考虑 n \le 3 的情况,原来的转移会变成矩阵,感兴趣的读者可以先做下 BZOJ3328 PYXFIB ,与 n = 1 是本质相同的,并且可以发现 c(i) 仍然是一个常数,同理处理下再卷积即可。

READ MORE

考虑最暴力的做法,列出 n 个生成函数,FWT 到一起,复杂度 \mathcal O(n \times 2^k \times k) ,显然不能通过。

考虑三元组 (a_i, b_i, c_i)ans_k 的贡献,等价于三元组 (0, a_i \operatorname{xor} b_i, a_i \operatorname{xor} c_i)ans_{k \operatorname{xor} a_i} 的贡献。考虑这样将题意转化后,生成函数只有 0a_i \operatorname{xor} b_ia_i \operatorname{xor} c_i 下标上有值(分别为 a, b, c)。那么经过一次 FWT 后,只有四种值,分别为 a+b+c, a+b-c, a-b+c, a-b-c

考虑将 n 个生成函数加起来做 FWT ,假设 a+b+c, a+b-c, a-b+c, a-b-c 分别在其中出现了 x, y, z, w 次,那么这个位置在正常做法情况下的值应该为 (a+b+c)^x \times (a+b-c)^y \times (a-b+c)^z \times (a-b-c)^w ,也就是说我们需要解出这个 x, y, z, w 的值。

首先显然的 x + y + z + w = pp 是这位上当前的值。需要注意的是,这个 a, b, c 并不一定需要是题目中给出的,所以我们可以分别取 (0, 1, 0)(0, 0, 1) ,列出两个方程,此时我们若再通过改变 (a, b, c) 来列方程,则可以通过两个已有的来表示,本质相同的,需要考虑别的方式得到新的方程。

考虑构造一个新的多项式,对于每个 k = b_i \operatorname{xor} c_ik \text{+=} 1 ,这样的话可以得到一个新的方程 x + y + z + w = qq 是这位上当前的值。

这样的话我们就得到了四个本质不同方程,可以解除上面的 x, y, z, w ,得出正常 FWT 后应该得到的点值,再将其 IFWT 一次即可得到答案。

READ MORE

DP 。用 f_{u, 0} 表示 u 点被染黑的概率,f_{u, 1} 表示 u 点被染白,但是其祖先中有点被染黑的概率,用 f_{u, 2} 表示 u 点被染白,且其祖先没有被染黑的点的概率。所求答案即 \displaystyle{\sum_{i=1}^n f_{i, 0}}

READ MORE

考虑一段数 a_{l..r} 是公差为 k 的等差数列,当且仅当:

  • \max a_{l..r} - \min a_{l..r} = k(r - l)

  • \gcd abs(a_i - a_{i-1}) = k, (i \in (l, r])

  • \max pre_{l..r} < lpre_i 表示 a_i 上一次出现的位置。

线段树维护一下即可。

READ MORE

榕树还是当年的榕树,你却不是当年的你了……

先点名表扬下这个题面,写的也太优美了吧 QAQ ...

假设我们只需要判断 1 号点能否成为最后的答案,用 f_i 表示取完 i 所在的子树的所有点后榕树的心离 i 的最近距离,那么答案即求 [f_1 = 0].

考虑 f_u 怎么求,最难消去的孩子是 \max (siz_v) (v \in son_u) 的孩子 v ,可以用其他子树的 siz 来填补这棵子树。代码中,另一部分的大小表示为 half ,这一部分表示为 f[max]

对于不以 1 为根的情况,可以把根节点到当前点 u 的路径缩成一个点来考虑,可以上下 DP 。

READ MORE