ss讲课day1

网页：https://vjudge.net/contest/684804#overview

简单计数基础

A

注意到一个东西，从一个数 $z$ 变成 $x$ 的方法不唯一

因此先考察一个简单的问题：一个数 $z$ 能不能变成 $x$ ？

性质1：

如果第某一位使用了一次四舍五入后，它以后都不会有机会往后进位了 换一种说法是，前面的数至多能对后面的数产生 $1$ 的贡献，证明可以使用数学归纳法来完成

因此可以认为从小位往大位来 dp 是合理的

因此考虑状态 $f[n][0/1]=true/false$ 表示从小往大操作与匹配，前 $n$ 位匹配成功并且钦定第 $n$ 位往 $n+1$ 位 会/不会 进位这一要求能不能达到

回归到原问题上

事实上刚刚的问题帮助你获得了一个检验数 $z$ 能否变成 $x$ 的策略，因此考虑在这个检验的动态规划状态上动态dp，因此就有 $dp[n][a/b][c/d]$ 表示前 $n$ 位匹配成功且要求检验的 dp 数组的状态为 $f[n][0]=a/b$,$f[n][1]=c/d$ 的数有多少，这实际上是一个 数位dp 加上 dp套dp

B - 这是 NOIP2024T3

一看这个题会发现一个问题：以不同的边作为起点所形成的树是有可能重叠的，不能简单的做加法

不妨先思考一下简单的情况：如果如果只有一个边作为起点，那么是怎么样的？

事实上手玩一下就能发现如果钦定了起始边，然后像一棵树一样把所有边展开，那么实际上方案数就是每个节点的儿子数的阶乘的乘积，这是因为：一坨共用同一个点的边在遍历顺序中就是一条链

性质1：

固定了一个起始边，那么由这个边能生成的树的个数是 $bas=\prod (deg[i]-1)!$

然后考虑第另一个特殊的情况：什么样的遍历顺序可能会同时被两条起始边同时计算到？

实际上就是上文所说的那个遍历顺序中一条链的开头和结尾被固定的情形

那么多个起始边呢？

性质2：

这些边要构成一条链，而不能出现分叉的情形，不然就不可能同时由这些起始边弄出一个共有的遍历顺序

性质3：

在这条特殊的链上的每个点上，开头和结尾是固定的，但是其他位置就不固定了，因此，这个点的贡献由 $\prod (deg[i]-1)!$ 变成 $\prod (deg[i]-2)!$，因此需要给这个链上的每个点 $i$ 乘以 $\frac 1 {deg[i]-1}$

容斥

令 $A_i$ 表示由 $i$ 条特殊边共同生成的树的个数，那么

$$ans=\sum_{i\ge1}A_i\cdot (-1)^{i-1}$$

过程中不难发现我们不关心哪些边被计数到了，我们只关心计数到了多少边，因此可以考虑在往集合里加边的时候同时乘以 $-1$ ，这是一个很常见的套路

首先为保证补充不漏，我们钦定每一条链的贡献在其 lca 处被计算，因为 $(-1)^x$ 这个东西是可以结合的，然后考虑转移：

令 $f[i]$ 表示以 $i$ 为根的子树的上述的这些权值的和，如果某条边是特殊边，那么考虑将其加入到计算内，有

$$f'[i]=f[i]+(-1)\cdot f[i]+1=1$$

否则就是维护子树和即可：

$$f[i]=\sum_{j\in son[i]}f[j]$$

C

大体思路

注意到题目要求的是可重集对数，因此我需要知道左右两边的可重集合里有多少种元素后还需要用一个组合数来求解

最朴素的暴力，枚举左边的集合出现了哪些数字 $\mathbb S$ ，然后想办法处理一下左边点对于右边选数字会产生那些影响与限制，就是两种：

• (a)右边集合的某些数字必选，记这些数字的集合为 $\mathbb T$

• (b)有若干个形如 “$a[i],b[i]$ 中至少选一个的” 的限制

我们将题目中的 $a[i],b[i]$ 限制放在图上，那就相当于给点连边，而我们枚举左边集合出现的数字实际上是在枚举图上的点集，那么看看这两种限制是怎么产生的:

如果在原来的图中某条边连接的两个点其中一个出现在左边的集合中，而另外一个没有出现，那么另外一个就必须出现在右边的集合中，这是 (a)限制如果在原来的图中某条边连接的两个点都出现在了左边的集合里，那么这条边就转化成了 (b)限制，如果在原来的图中某条边连接的两个点都没有出现在左边的集合里，那么这样的左边的集合是不合法的

然后可以注意到，其实 (b)限制 拍在图上是 原图对于点集 $\mathbb S$ 的导出子图，而选择右边集合就是在这个导出子图进行染色，使得导出子图的每一条边所连接的两个点中至少有一个点被染色了

因此可以把右边点集 $\mathbb G$ 拆成两部分: $\mathbb{G=T \cup S'}$，其中 $\mathbb S'$ 表示 $\mathbb S$ 的导出子图中符合 (b)限制 的染了色的点集

不过在此之前还需要把原图里没有任何边的点提前抽出来，扔到集合 $\mathbb X$ ，这些点可以加也可以不加，其余的至少有一个边连的点扔到集合 $\mathbb Q$ 里头

然后考虑怎么计算这个过程：

我们记 $F(a,\mathbb B,\mathbb C)$ 表示大小为 $a$ 的可重集，其中 $\mathbb B$ 中元素必须全部出现，然后还有 $\mathbb C$ 中的元素可以出现也可以不出现

首先枚举 $\mathbb S$ 并检查 $\mathbb S$ 是否合法，接着很容易导出 $\mathbb T$ ，然后再枚举 $\mathbb {S' \subseteq S}$

然后检查 $\mathbb S'$ 是否符合 (b)限制 ，如果均能通过上述检验，那么 $ans+=F(n1,\mathbb S,\mathbb X)\cdot F(n2,\mathbb {S' \cup T},\mathbb X)$

优化

• 具体的，你关注到其实想要计算 $F(a,\mathbb B,\mathbb C)$ 你不需要 $\mathbb B,\mathbb C$ 而是需要 $|\mathbb B|,|\mathbb C|$

• 另外一点，就是 $\mathbb S'$ 符合 (b)限制 的一个等价命题是: 点集 $\mathbb{U=S - S'}$ 的导出子图是一个独立集

然后实际上有 $\mathbb{Q - U = T\cup S'} \Longrightarrow \mathbb{|T\cup S|=|Q|-|U|}$

因此就有 $ans+=F(n1,|\mathbb S|,|\mathbb X|)\cdot F(n2,|\mathbb Q|-|\mathbb U|,|\mathbb X|)$，这里只要求：

• $\mathbb U$ 是独立集（这只与 $\mathbb U$ 有关，与 $\mathbb S$ 无关，我们成功分离了 (b)限制 里的捆绑的关系）

• $\mathbb {S' \subseteq S} \Longleftrightarrow \mathbb {U \subseteq S}$

所以可以先把所有独立集 $\mathbb U$ 求出来，并给数组 $f[\mathbb U]$ 赋值为 $F(n2,|\mathbb Q|-|\mathbb U|,|\mathbb X|)$ ，对 $f[]$ 做一遍高维前缀和，然后枚举所有合法的 $\mathbb S$ 使得 $ans+=F(n1,|\mathbb S|,|\mathbb X|)\cdot f[\mathbb S]$

D

设 $f[x=i]$ 表示值恰好为 $i$ 的方案数，那么答案就是求

$$ans=\sum_{i\ge 0} f[x=i]\cdot i$$

考虑进行阿贝尔变换，得到：

$$\begin{aligned} ans&=\sum_{i\ge 0} (f[x\ge i]-f[x\ge i+1])\cdot i \\&=f[x\ge 0]\cdot 0 + \sum_{i\ge 1}f[x\ge i] \\&=\sum_{i\ge 1}f[x\ge i] \end{aligned}$$

然后考虑 $f[x\ge i]$ 有什么组合意义： 先把序列里头所有小于 $i$ 的数全部染成黑色，假设有 $cnt$ 个黑色，然后把这些黑色块填入到方阵中，使得不存在某一行某一列全为黑色的 统计有多少种填法，记为 $F$ ，则 $f[x\ge i]=F\cdot cnt!\cdot (nm-cnt)!$

于是这就须要求 $G[i]$ 表示用恰好 $i$ 个黑色块，无法使得某一行某一列全为黑色的填法 那么就是有 $n+m$ 个限制，形如

• (a) $A_i$ 表示第 $i$ 行存在至少一个白色，其中 $1\le i \le n$
• (b) $A_i$ 表示第 $i-n$ 列存在至少一个白色，其中 $n+1\le i \le n+m$

那么有

$$G[i] = |\cap_{i=1}^{n+m}A_i|$$

这种限制很不好弄，但是每个限制的补集却十分的简洁：某一行或某一列全为黑色 那么考虑容斥，就是枚举强制违反那些限制，忽略其他限制，而不难发现这个东西可以使用一个组合数来计算，并且你只关心违反了几个行限制，几个列限制，具体是谁并不关心，因此这是一个二项式反演，然后推式子

$$\begin{aligned} \eta\in \mathbb N,G[\eta]&=\sum_{x=0}^n\sum_{y=0}^m (-1)^x\binom n x\cdot (-1)^y\binom m y \cdot \binom {(n-x)(m-y)} \eta\\ &=(-1)^{n+m}\sum_{x=0}^n\sum_{y=0}^m (-1)^x\binom n x\cdot (-1)^y\binom m y \cdot \binom {xy} \eta\\ &=\sum_{r=0}^{nm}\binom r \eta \sum_{\substack{xy=r\\ 0\le x\le n\\0\le y \le m}} (-1)^{n+m-x-y}\binom n x\binom m y \end{aligned}$$

显然后面那一坨仅与 $r$ 相关，且是可以提前预处理的，记为 $v'[r]$ 则

$$\begin{aligned} G[\eta]&=\sum_{r=0}^{nm}\binom r \eta \cdot v'[r]\\ &=\frac 1{\eta!}\sum_{r=\eta}^{nm}(\frac 1 {(r-\eta)!})\cdot(r!\cdot v'[r]) \end{aligned}$$

显然这是一个卷积的形式，因此使用多项式乘法即可 把 $G[i]$ 处理出来后计算总和只需要对 $a_i$ 排个序即可，时间复杂度是 $\mathcal O(nm \log nm)$ 的

E

好玩题，事实上，你们应当反应过来：求期望为什么不取模

事实上 $np\le 20$ 告诉你，失败的概率理论上不会特别大

首先考虑 $k$ 充分大的情况

那么实际上就是我每次失败都会使用道具，所以每次期望进到下一层的期望步数是 $\frac 1 {1-p}$，因此答案为 $\frac n {1-p}$

事实上，经检验，当 $k\ge 200$ 的时候，这个估计是符合要求的

然后考虑当 $k$ 不是很大的时候

你需要注意到一个性质

性质1：

你的道具更愿意留在后面使用：也就是说，如果在第 $i$ 层失败了，如果不使用道具，那么在第 $j(j<i)$ 层失败了之后都不会使用道具

可以推导出，从第 $i$ 层在不使用道具的条件下走到 $i+1$ 层的期望步数为 $(\frac 1 {1-p})^{i+1}$

因此令 $f[i][j]$ 表示目前走到第 $i$ 层，且还剩 $j$ 个道具的时，到结束游戏的最优策略的期望

$$f[i][j]=\min(1+p\cdot f[i][j-1]+(1-p)\cdot f[i+1][j],f[i+1][j]+(\frac 1 {1-p})^{i+1})$$

F

容斥入门题

令 $f_i$ 表示前 $i$ 个家族恰好且第一次构成后 $\sum_{k\le i}h_i$ 名的方案数（只计算这 $i$ 个家族的相对排名，其他不管），那么你需要做的就是把可能在 $i$ 以前就出现过的恰好满足的情况给去掉，即

$$f_i=(\sum_{k\le i}h_k)!-\sum_{k<i}f_k\cdot(\sum_{k<j\le i}h_j)!$$

而最后

$$ans=n!-\sum_{i=1}^Hf_i\cdot(n-\sum_{j\le i}h_j)!$$

G

需要注意到一个性质：

性质1：

删除的数一定是最小的若干个数

因此考虑这么一个过程：

每次从集合中移除最小的那个数，直到最大公因数和最小值不相等的时候

由此产生了性质2：

不会删除超过 $\log n$ 个数

因此这个题目被拆分成了两个过程：

(1)删除 (2)终止状态

求出 $f_{A,B}$ 表示最大公因数为 $A$ 且集合里的元素的个数为 $n-B$ 的集合有多少，

显然有

$$f_{A,B}=-\binom{\lfloor\frac m A\rfloor-1}{n-B-1}+\sum_{A|C}\mu(\frac C A)\binom{\lfloor\frac m C\rfloor}{n-B}$$

之后令 $g_{A,B}$ 表示从 $A$ 开始，每次选取上一轮元素的因子，这样做 $B$ 轮得到的路径数

$$g_{A,B}=\sum_{C|A}g_{C,B-1}$$

最后答案为：

$$ans=\sum_{A\le m,B\le \log n}g_{A,B}\cdot f_{A,B}\cdot (n-B)$$

H

令 $f[u][i]$ 表示以 $u$ 为根的子树内，$u$ 的相对排名为 $i$ 的方案数

转移：

考虑将 $u$ 的子树 $v$ 插入 $u$ 的序列中，设在 $u$ 前插入了 $x$ 个元素，那么在 $u$ 后插入了 $siz[v]-x$ 个元素，那么如果 $u > v$ 那么 $v$ 在自己子树内的排名要在 $x$ 以前，否则要在 $x$ 以后，所有用一个前缀和维护一下就行了

I

首先考虑朴素的解法:

对于任何一幅图片，我只关心它被访问过多少次，以及当前的总和是多少，因此： 令 $f[x,i,j,k]$ 表示第 $x$ 幅照片，总共访问了 $i$ 轮，其中除了 $x$ 以外的 $+1$ 访问了 $j$ 次，除了 $x$ 以外的 $-1$ 访问了 $k$ 次的概率 然后可以借助 $i,j,k$ 的值来计算出当前状态的所有参数，从而计算转移到下一步的概率，时间复杂度 $\mathcal O(nm^3)$ 不难发现这个做法中的很大一部分时间复杂度都是由于符号引起的，如果能把符号去掉就好了

然后不妨思考一个东西：

要是所有照片都是 $+1$ 的就好了 如果所要照片都是 $+1$ 的话，那么对于每个照片，我只要关心他被访问多少次即可， 因此记 $f[x,i,j]$ 为第 $x$ 幅照片，总共访问了 $i$ 次，其中访问了它 $j$ 次的概率 然后考虑一下进行第 $i+1$ 次访问时看看有多大的概率会访问到它： $p=\sum_{j=0}^{i}f[x,i,j]\cdot \frac{w_0+j}{wtot+i}=\frac 1 {wtot+i}\sum_{j=0}^i f[x,i,j]\cdot(w_0+j)=\frac{\mathbb E(w)}{wtot+i}$ 这就很有意思了，你发现某一次访问某个照片的概率与具体访问过它几次无关，而与它当前的期望有关 而由于期望是线性的，某个照片当前的期望就是每一步访问它次数的期望之和，这个玩意儿可以写成一个递推式： $\mathbb E_{n+1}=\mathbb E_n+\frac{\mathbb E_n}{wtot+n}=\mathbb E_0 \cdot \prod_{i=0}^n (1+\frac 1 {wtot+i})$

怎么创造所有照片的符号都相同这一个条件呢

那就是计算出来，在 $m$ 次访问中,访问了 $k$ 次 $+1$ 的概率 这个可以用一个 $\mathcal O(m^2)$ 的 dp 来计算，然后统计答案时只需要计算条件期望的和就行了 就是 $\mathbb E(x)=\sum \mathbb p(某种情况发生的概率)\cdot \mathbb E(这种情况必然发生的前提下的x)$

J

转化一下题意：

每个球有一个到达零点的时间 $\frac {x_i} {v_j}$ ，总共至多有 $nm$ 种不同的时间

枚举时间 $t$，然后对于每个球考虑它有两种可能，在 $t$ 时刻它没过零点 $(x+v\cdot t\le 0)$ ，和它已经过了零点

然后就是对这 $n$ 个球进行一个背包，每个球以一定的概率染成黑白色，则 $P(ans\le t)$ 即为黑色个数大于 $\lceil \frac n 2 \rceil$

考虑优化，因为现在的时间复杂度是 $O(n^2m^2)$ 的

考虑时间的瓶颈：重构背包花费了大量的时间

我们将时间排序，那么实际上每个球的修改量的总和是 $O(nm)$ 的，然后可以考虑退背包

因此时间复杂度是 $O(nm^2)$ 的

K

实际上是对于每个询问要求选出一个子树使得该子树与给定的路径有交

为了保证不重不漏，我们钦定一个子树在它与这条链的交的深度最小的节点处被统计

换根dp 即可

令 $f_u$ 表示在以 $u$ 为根的子树中，$u$ 必选有多少种选法；

令 $g_u$ 表示以 $u$ 为整棵树的根，$u$ 必选，$u$ 的父亲那一个方向选取的方案数

转移：

$$f_u=\prod_{v\in son[u]}(f_v+1)\\ g_u=1+g_{fa[u]}\times\prod_{\substack{x\in son[fa[u]]\\x\not= u}}(f_x+1)$$

然后倍增维护一下路径上的节点的和即可

L

虚树+dp