CF1874(CF Round 901) 总结

CF1874(CF Round 901) 总结

A

显然若干轮之后，每两次操作不会改变它们的苹果，于是让 \(K\) 对一个较小数取 \(\min\) 然后暴力做即可。

B

每一位是独立的，对于 \(a,b,m\) 都相同的位，操作后的结果一定相同，所以只有 \(8\) 个本质不同的位。

我们从 \(a=(11110000)_2,b=(11001100)_2,m=(10101010)_2\) 开始跑最短路，这样就能覆盖所有本质不同的位的情况。跑出所有 \((a',b')\) 的最短路，这时还有一些位是没有限制最终的 \(a'=c,b'=d\) 的，可以用五进制把所有情况压起来，没有限制的位记为 \(4\)，那么按顺序枚举所有情况，为 \(4\) 的位可以随意替换为 \(0\sim 3\) 进行转移。

所有情况数为 \(5^8<4\times 10^5\)。

查询时，找出最多八个本质不同的位，然后转成五进制 \(O(1)\) 查询。

计算量为 \(16\times 2^{16}+8\times 5^8+30\times T\)。

C

设 \(f_i\) 表示从 \(i\) 开始走到 \(n\) 的最优步数。我们把 \(i\) 所有出边的 \(f\) 从大到小排序，同时处理 \(p_{i,j}\) 表示度数为 \(i\) 的点，走向第 \(j\) 条边的概率。那么两者按顺序相乘再相加即可求出 \(f_i\)。

怎么求 \(p_{i,j}\) 呢？我们每次肯定会选择待选序列中最大的点走。对于 \(j=1\)，有 \(p_{i,j}=\frac 1 i\)。否则，考虑为另一个人选的边 \(k\)，若 \(k<j\) 转化为 \(p_{i-2,j-2}\)，若 \(k>j\) 转化为 \(p_{i-2,j-1}\)。即 \(p_{i,j}=\frac {j-2}{i}p_{i-2,j-2}+\frac {i-j}{i}p_{i-2,j-1}\)。

复杂度 \(O(n^2+m\log n)\)。

D

设 \(f_i\) 表示当前在 \(i\)，第一次走到 \(i+1\) 的期望步数。答案为 \(\sum f_i\)。

\[f_i=1+\frac {a_{i-1}}{a_i+a_{i-1}}(f_{i-1}+f_{i}) \]

\[f_i=\frac {a_i+a_{i-1}}{a_i}+\frac{a_{i-1}}{a_i} f_{i-1} \]

推出前几项得

\[f_0=1 \]

\[f_1=1 +\frac {2a_0}{a_1} \]

\[f_2=1+\frac {2(a_0+a_1)}{a_2} \]

\[f_3=1+\frac{2(a_0+a_1+a_2)}{a_3} \]

\[\sum f_i=n+2\sum_{i} \frac {1} {a_i}\sum_{j=0}^{i-1} a_j \]

对其 DP，设 \(dp_{i,j}\) 表示考虑完前 \(i\) 项，\(a\) 的和 为 \(j\) 时的最小步数。直接做是 \(O(n^2)\) 的。

考虑优化：

\[dp_{i,j}=\min_{k<j} dp_{i-1,k}+\frac k {j-k} \]

其中贡献函数是满足四边形不等式的，所以可以分治决策点，复杂度 \(O(nm\log m)\)。

E

设 \(f_{i,j}\) 表示 \(|A|=i\)，且 \(\text {fun}(A)=j\) 的 \(A\) 的数量。枚举 \(A_1\) 的值，则拆成两个排列，有转移：

\[f_{x,y}=\sum _{i=1}^x\binom{x-1}{i-1}\sum_{j=0}^{y-x} f_{i-1,j}\times f_{x-i,y-x-j} \]

直接做是 \(O(n^6)\)。发现后面的式子是卷积的形式，我们写成卷积：

\[F_k(x)=\sum _{i=1}^k\binom {k-1}{i-1}\times x^k\times F_{i-1}(x)\times F_{k-i}(x) \]

考虑到 \(F_n\) 是 \(\frac {n\times (n+1)}{2}\) 次多项式，我们可以代入求 \(O(n^2)\) 个值，然后用拉插求出 \(F_n\) 的系数即我们要的答案。求值可以每次 \(O(n^2)\) 暴力求，复杂度 \(O(n^4)\)。

而对于拉插的部分，观察式子：

\[F(x)=\sum _{i=1}^T y_i\prod _{j=1,j\ne i}^T \frac {x-j}{i-j} \]

可以先处理 \(\prod _{j=1}^T (x-j)\)，对于多项式系数 \(a\)，每一项 \(a_i=a'_{i-1}-j\times a_i'\)。然后每次用 \(\prod _{j=1}^T (x-j)\) 除以 \((x-i)\) 即可，每一项 \(a_i'=(a_i-a_{i-1}')/(-j)\)。都是 \(O(n^4)\)。

总复杂度 \(O(n^4)\)。

F

考虑容斥，我们指定区间集合 \(S\) 都是坏区间，对于所有 \(S\)，求出 \((-1)^{|S|}\) 与 \(S\) 方案数乘积的和。

发现对于真相交的两个坏区间 \([l_r,r_1],[l_2,r_2]\) 满足 \(l_1<l_2\le r_1<r_2\)，一定有 \([l_1,l_2-1]\) 是坏区间。所以对于存在真相交区间的集合 \(S\)，我们选或不选 \([l_1,l_2-1]\) 都可以，那么容斥系数就抵消了，所以我们可以不用考虑存在真相交区间的集合。

剩下的区间一定是不交或包含的关系，组成树形结构。于是设 \(f_{l,r}\) 表示考虑完了 \([l,r]\) 所有子区间是否在 \(S\) 内，且 \([l,r]\in S\) 的带容斥系数的方案数。同时我们设 \(g_{l,r,x}\) 表示考虑完 \([l,r]\) 所有子区间是否在 \(S\) 内，且有 \(x\) 个位置不被 \(S\) 中的区间包含的带容斥系数的方案数。则有转移：

\[g_{l,r,x}=g_{l,r-1,x-1}-\sum _{i=l}^r g_{l,i-1,x}\times f_{i,r} \]

\[f_{l,r}=-\sum _{i=0}^{r-l+1} g_{l,r,i}\times i!,\text {when }r\le m_l \]

我们先算 \(g\)，再算 \(f\)，最后把 \(g_{l,r,0}\) 加上 \(f\)。复杂度 \(O(n^4)\)。