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\)。
推出前几项得
对其 DP,设 \(dp_{i,j}\) 表示考虑完前 \(i\) 项,\(a\) 的和 为 \(j\) 时的最小步数。直接做是 \(O(n^2)\) 的。
考虑优化:
其中贡献函数是满足四边形不等式的,所以可以分治决策点,复杂度 \(O(nm\log m)\)。
E
设 \(f_{i,j}\) 表示 \(|A|=i\),且 \(\text {fun}(A)=j\) 的 \(A\) 的数量。枚举 \(A_1\) 的值,则拆成两个排列,有转移:
直接做是 \(O(n^6)\)。发现后面的式子是卷积的形式,我们写成卷积:
考虑到 \(F_n\) 是 \(\frac {n\times (n+1)}{2}\) 次多项式,我们可以代入求 \(O(n^2)\) 个值,然后用拉插求出 \(F_n\) 的系数即我们要的答案。求值可以每次 \(O(n^2)\) 暴力求,复杂度 \(O(n^4)\)。
而对于拉插的部分,观察式子:
可以先处理 \(\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\),再算 \(f\),最后把 \(g_{l,r,0}\) 加上 \(f\)。复杂度 \(O(n^4)\)。