ARC098D Donation
题意:一张无向连通图,\(n\) 个点 \(m\) 条边。你一开始选择任意一个点开始走,到达点 \(u\) 时,要求你必须有 \(a_u\) 元,且可以在点 \(u\) 捐赠 \(b_u\) 元。可以以任意一点结束,求在所有点捐赠一次的前提下,你的最小初始钱数。 \(1\le n\le n,m\le 10^5\)
考虑倒着来,到达一个点 \(u\) 的条件是手里至少有 \(\max(0,a_u-b_u)\) 元,第一次到达 \(u\) 后可以赚钱 \(b_u\) 元。不妨设 \(c_u=\max(0,a_u-b_u)\)
从 \(u\) 走到 \(v\),我们走的一定是 \(c\) 最大值最小的那条路径。
因此考虑构建 Kruskal 重构树(边权是两个端点的 \(c\) 较大值),发现我们一定是从一个叶子开始走,一个子树会先走完里面的点再走外面的点。
考虑 dp,设 \(f[u]\) 表示走完 \(u\) 子树的最小初始钱数。枚举初始从哪个儿子子树开始走,且走到 \(u\),设为 \(v\)。那么
\[f[u]=\min_v\{\max(f[v],c[v]-s[u])\} \]其中 \(s[v]\) 表示 \(v\) 子树内 \(b\) 的总和,时间复杂度 \(O(m\log m)\)。
CF715E Complete the Permutations
题意:两个排列 \(p,q\),长度都是 \(n\)。定义 \(w(p,q)\):每次交换 \(p\) 中的两个数,将 \(p\) 变成 \(q\) 的最少交换次数。现在两个排列中有一些数字未知(标记为 \(0\)),求对于所有 \(i(0\le i<n)\),有多少种可能的 \(p,q\) 满足 \(w(p,q)=i\),答案摸 \(998244353\)。
最少操作次数,把 \(p_i\to q_i\) 连边,间接相当于形成环数量。
去掉已经形成的环,我们会剩下四类边:
-
\(x\to y\)
-
\(0\to x\)
-
\(x\to 0\)
-
\(0\to 0\)
对于第一类,我们把 \(x,y\) 合并成一个点,那么相当于我们有一些点,有四种属性:
-
两端没有 \(0\)
-
左端有 \(0\)
-
右端有 \(0\)
-
两端都有 \(0\)
分别计算这四种点的个数。然后发现,如果将第四种点和第二或三种点合并,还是第四种点;如果将第四种点和第一种点合并,会变成第二或三种点;第二或三种点可以和同种点合并;一个第二或三种点,可以自己形成一个环。
注意到每个第四种点都一定会一个第一种点合并。考虑一个最终的环,分为包含第四种点和不包含两大类。
如果不包含,那么环内都是第二或三种点,且不同时包含两种点。
如果包含,定义 \(A\) 为一个第四种点和二、三种点进行若干次合并后的点,\(B\) 为第一种点,不难发现最终的环一定是形如 \(ABAB...\) 这样的。显然,第二、三种点和这个步骤是独立的,可以分开计算,然后这个就直接用第一类斯特林数乘个阶乘。
现在考虑第二、三种点如何分配,枚举不包含第四种点的环的个数以及内部的点的个数总和,然后将剩余的分配下去。显然两种点是独立的,可以分开计算。
时间复杂度 \(O(n^2)\)。
AGC034F RNG and XOR
题意:一个变量 \(x\),初始值为 \(0\),每次随机选择一个 \([0,2^n)\) 内的数 \(y\),概率为 \(\frac{a_y}{\sum_i a_i}\),然后 \(x\gets x\operatorname{xor} y\)。对于每个 \(i(i\in [0,2^n))\),求出 \(x\) 第一次变为 \(i\) 的期望次数,答案模 \(998244353\)。 \(1\le n\le 18\)
选到 \(i\) 的概率为 \(p_i=\frac{a_y}{\sum_i a_i}\)。显然有个 dp,设 \(f[i]\) 表示变为 \(i\) 的期望次数。
\[f[i]= \begin{cases} 0 & i=0\\ \sum\limits_j 1+p_j\cdot f[i\operatorname{xor} j] & i\not =0 \end{cases} \]高斯消元是 \(O(n^{3n})\) 的,无法通过。
令 \(f\) 和 \(p\) 的集合幂级数分别为 \(F(x),P(x)\)。
则 \(F(x)=\sum\limits_S x^S + F(x)*P(x)\)
但是 \(f[0]\) 是已知等于 \(0\) 的,上式其实是不成立的。
考虑修正 \(f[0]\):\(F(x)+c=\sum\limits_S x^S+F(x)*P(x)\)
显然 \(c\) 是常数。把两边的系数相加,即可得到 \(c=2^n\):\(F(x)+2^n=\sum_S x^S +F(x)*P(x)\)
整理得
\[F(x)=\frac{\sum_S x^S-2^n}{1-P(x)} \]集合幂级数是无法求逆的。但这里比较特殊,如果我们给 \(f[0...2^n-1]\) 全部加上 \(t\),由于 \(P(x)\) 的系数总和为 \(1\),\(F(x)+2^n=\sum_S x^S + F(x)*P(x)\) 仍然成立,那么 \(F(x)=\frac{\sum_S x^S-2^n}{1-P(x)}\) 也成立。因此我们先通过 fwt 相除的方式求出一个 \(F(x)\),然后通过整体偏移的方式修正 \(f[0]\)。时间复杂度 \(O(n2^n)\)。
标签:总结,2024.2,le,frac,19,sum,合并,第四种,三种 From: https://www.cnblogs.com/Sktn0089/p/18020740