小红书笔试（2024）3.17

记录一下。
第三题题目大概意思：给定一个整数数组（长度<1e5，数据范围0~1e9)，每次随机选择一个数调整，求第一次所有数都为偶数时数组和的期望值。

做法：搞个函数f(k,n-k)表示n个数中奇数为k个的期望调整次数，为方便起见，f(k,n-k)写为f(k)
          期望转移表达式为 f(k) = f(k-1)*k/n + f(k+1)*(n-k)/n + 1
          记录a_k = f(k) - f(k-1)
          上式转化为等比数列，即a_k = (n-k)/k * a_{k+1} + n / k
          考虑到边界为a_n = f(n) - f(n - 1) = 1，可以直接循环一遍算出所有a_k值
          若原数组奇数个数为u，则答案为(\sum_{1}^{u} a_k) + f(0)， 而f(0)为0
          乘法逆元的话直接线性筛或者快速幂。 时间复杂度O(n)