多校A层冲刺NOIP2024模拟赛08
T1 传送 (teleport)
签到题
性质题，注意到对于一个点而言有意义的传送的只有分别按 \(x,y\) 排序后与其相邻的点，证明考虑贪心手模即可。
然后就能上最短路了，dj 的时间复杂度为 \(O((n+m)logn)\)。
T2 排列 (permutation)
签到题
状压，注意到 \(\dfrac{n}{k}\) 最大不超过 \(10\)，则只需考虑这 \(10\) 个数是否相邻即可，直接状压 \(DP\) 计算只有这 10 个数的方案（若相邻互质则强行塞一个数），然后插板法放回原序列即可。
记 \(t=\frac{n}{k}\) 时间复杂度为 \(O(2^tt^3+n)\)。（爆标了^^。可以进一步推性质优化状压，还能打表优化，思路来自 xlrong）
T3 战场模拟器 (simulator)
签到题
势能线段树（最基础版），注意到每个人只会死亡一次，每个护盾只会抵挡一次，并且这两个东西的上限都是 \(O(n)\) 级别的，在线段树上直接下放解决即可。
时间复杂度为 \(O(nlogn)\)。
T4 点亮 (light)
题意转化，概率DP，二项式反演
很有意思的一道题，感觉 subtask3 也想不到。
先讲讲 \(n≤1000\) 怎么做
首先题意转化一下，称一条边合法当且仅当它能被点亮一次，考虑一种好的方式能更好的统计信息。由预设型 \(DP\) 启发想到按编号从大到小去加边去填写这个图，这样能使信息更具体，并且使得信息没有后效性，那么就可以 \(DP\) 了。
定义 \(f_{i,j}\) 表示 \(i\) 个点还未连边（记为散点），形成了 \(j\) 个连通块时的概率，初始状态 \(1\to f_{n,0}\)，答案即求 \(f_{0,k}\)。
由于是从大到小加边所以很好转移，分讨一下这条边两端是啥点即可。
散点+散点：产生一个新的联通块，消耗两个散点。
非散点+散点：消耗一个散点。
非散点+非散点：无需转移，因为此时使用的概率 \(DP\)，此时已经把这种情况给计算了，这就是概率 \(DP\) 的优越性所在。
概率 DP，只能考虑当前状态的下一步（这样才好计算不同情况的概率），即只能用刷表法转移，以上分讨简单计算一下概率转移即可。
时间复杂度为 \(O(Tn^2)\)。
正解
注意到一个联通块内被点亮两次的边只会有一条（记其为关键边），所以题目所求即为恰有 \(k\) 条关键边的概率。
恰有这个限制太强了，考虑弱化这个限制，套路考虑二项式反演由恰好 \(\to\) 钦定。
记 \(f_i\) 表示钦定 \(i\) 条关键边的概率，\(g_i\) 表示恰好 \(i\) 条关键边的概率。
根据方程定义显然有
\[ f_n=\sum_{i=n}^m\binom{i}{n}g_i \]由二项式反演得
\[ g_n=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}f_i \]考虑计算 \(f_i\)，设 \(S\) 为一种选择关键边的方案，则有\(f_i=\sum_{|S|≥i}P(S)=cnt_{|S|≥i}P\)。显然在钦定完关键边后每种方案的概率是相等的，所以可以分为两部分考虑，即 方案的概率 \(\times\) 方案数。
- 第一部分，计算方案的概率。因为得满足已经钦定好的边必须为关键边，所以得保证这些边周围边的编号小于它，所以还是考虑从大到小一条边一条边的加入。
定义所有还未填好钦定的边及其两个端点有关的边为有关边，其他边则为无关边（注意此时无关边的定义）。
因为限制变为了恰好，所以在计算概率时不用考虑无关边（因为就算无关边成为了关键边也并不与方程定义相悖）。
现在还是不好直接做，考虑钦定一种填关键边的顺序，再乘上全排变得好做。
那么答案就变为了每条关键边概率的乘积，而一条关键边的概率即为 \(\dfrac{1}{cnt_{有关边}}\) （因为此时已经钦定了添关键边的顺序所以分子是 \(1\) ）。
所以（分母考虑计算补集即可）。
- 第二部分，计算方案数。比较平凡，直接上式子吧 \(\dfrac{A_{n}^{2i}}{i!2^i}\)。
即能在 \(O(n)\) 解决一次回答。
所以时间复杂度为 \(O(Tn)\)。
p
