4.18 冲刺清北营 2
T1 操作
设 \(q_i=1-p_i\)
把结果式子拆开，发现对于一个选择加法的位置 \(i\)，\(a_i\) 的系数是后面所有选择乘法位置的 \(b\) 的乘积。因此我们可以把贡献提出，考虑每个位置 \(i\) 以及后面的贡献在累加。
如果只考虑选择乘法的位置，可以写出一个生成函数的形式 \(\prod_i [(1-p_i)b_ix+p_i]\)，这样 \([x^k]\) 表示有 \(k\) 个数产生贡献的系数与概率的乘积。但由于 \(i\) 后面的后缀 \([i+1,n]\) 中可以存在选择加法的，这样需要在统计答案时单独处理方案数，很不好做。
尝试把定义由有 \(k\) 个数产生系数贡献修改成后面是长度为 \(k\) 的后缀，这样被计入后缀的贡献是 \(q_ib_i+p_i\)，而没有被计入的贡献是 \(1\)，按照上面写成生成函数就是 \(\prod_i [(q_ib_i+p_i)x+1]\)。
求积可以分治优化，复杂度是 \(O(n\log^2 n)\)。
最后统计答案时枚举每个元素 \(i\) 以及其放置的位置 \(k\)，需要容斥，因为我们并没有考虑后缀 \([k+1,n]\) 与枚举的位置 \(k\) 上放了重复元素的情况，后缀 \([k,n]\) 的情况只需要在 \([k+1,n]\) 的容斥后答案的基础上单步容斥。同时还要卷积得到的是无序集合，要乘上方案数 \(k(n-1-k)!\)，最后总答案除以 \(n!\) 即为期望，复杂度是 \(O(n^2)\)。
考虑降低这个统计答案的过程，最后要求的多项式就是：
这可以分治去做，需要维护：
转移是：
最终复杂度 \(O(n\log^2 n)\)。
T2 选数
答案是对 \(\gcd\) 求和，套路性地去想到枚举 \(\gcd\) 为 \(i\) 的倍数的情况，从大到小枚举可以 \(O(n\log n)\) 容斥求出 \(\gcd\) 恰好为 \(i\) 的方案数。
设值域为 \(m\)，求异或和为 \(s\) 的直观做法是 FWT，单次 \(O(m\log m)\)，设定阈值 \(B\)，\(i\le B\) 时 FWT，复杂度为 \(O(Bm\log m)\)。
当 \(i\) 较大时，容易注意到 \(i\) 的倍数较少，而 \(k=4\) 代表着可以 meet in the middle，以 \(O(\left\lfloor m/i\right\rfloor^2)\) 的复杂度单次计算，总复杂度大致有一个上界 \(O\left(\dfrac{m^2}{B}\log m\right)\)，取 \(B=\sqrt{m}\) 可以得到理论最优复杂度 \(O(m\sqrt{m}\log m)\)。
上面的计算都存在一个问题——卷积或是直接暴力计算时会出现同一个元素被选取多次，需要手动容斥去掉不合法的情况，有较多细节。