Subsequences with a Unique Middle Mode II

1// Recall from solution 1 that after counting all the subsequences with `a` as2// the middle mode number, we need to subtract the cases where `a` is not a3// unique mode or not a mode.4//5// To avoid the need of looping through all numbers that are not `a`, we can6// maintain the sums that are not related to `a` in the loop.7//8// So, during the simplification of the formula, keep the running sums of9// pss, spp, pp, ss, and ps as the first item.10// (for cleaner notation, abbreviate p[b] and s[b] to just p and s)11//12//   sum(b != a) (p[a] * p * s) * (r - sa - s)13//             + (sa * s * p) * (l - p[a] - p)14//             + (p, 2) * sa * (r - sa)15//             + (s, 2) * p[a] * (l - p[a])16//17//   sum(b != a) (p * s) * (p[a] * (r - sa)) + (p * s^2) * (-p[a])18//             + (s * p) * (sa * (l - p[a])) + (s * p^2) * (-sa)19//             + (p^2 - p) * (sa * (r - sa) / 2)20//             + (s^2 - s) * (p[a] * (l - p[a]) / 2)21 22class Solution {23 public:24  // Same as 3395. Subsequences with a Unique Middle Mode I25  int subsequencesWithMiddleMode(vector<int>& nums) {26    int ans = 0;27    unordered_map<int, int> p;  // prefix counter28    unordered_map<int, int> s;  // suffix counter29 30    for (const int num : nums)31      ++s[num];32 33    long pss = 0;34    long spp = 0;35    long pp = 0;36    long ss = 0;37    long ps = 0;38 39    for (const auto& [_, freq] : s)40      ss = (ss + static_cast<long>(freq) * freq) % kMod;41 42    for (int i = 0; i < nums.size(); ++i) {43      const int a = nums[i];44      long sa = s[a];45      const long pa = p[a];46 47      // Update running sums after decrementing sa.48      pss = (pss + pa * (-sa * sa + (sa - 1) * (sa - 1))) % kMod;49      spp = (spp - pa * pa) % kMod;  // (-sa + (sa - 1)) * pa * pa50      ss = (ss - sa * sa + (sa - 1) * (sa - 1)) % kMod;51      ps = (ps - pa) % kMod;  // -pa * (-sa + (sa - 1))52 53      sa = --s[a];54 55      const int l = i;56      const int r = nums.size() - i - 1;57 58      // Start with all possible subsequences with `a` as the middle number.59      ans = (ans + nC2(l) * nC2(r)) % kMod;60 61      // Minus cases where frequency of `a` is 1, so it's not a mode.62      ans = (ans - nC2(l - pa) * nC2(r - sa)) % kMod;63 64      // Minus the values where `b != a`.65      const long pss_ = (pss - pa * sa * sa) % kMod;66      const long spp_ = (spp - sa * pa * pa) % kMod;67      const long pp_ = (pp - pa * pa) % kMod;68      const long ss_ = (ss - sa * sa) % kMod;69      const long ps_ = (ps - pa * sa) % kMod;70      const long p_ = l - pa;71      const long s_ = r - sa;72 73      // Minus cases where `a` is not a "unique" mode or not a mode.74      long subtract = 0;75      subtract = (subtract + ps_ * (pa * (r - sa))) % kMod;76      subtract = (subtract + pss_ * (-pa)) % kMod;77      subtract = (subtract + ps_ * (sa * (l - pa))) % kMod;78      subtract = (subtract + spp_ * (-sa)) % kMod;79      subtract = (subtract + (pp_ - p_) * sa * (r - sa) / 2) % kMod;80      subtract = (subtract + (ss_ - s_) * pa * (l - pa) / 2) % kMod;81      ans = (ans - subtract + kMod) % kMod;82 83      // Update running sums after incrementing p[a].84      pss = (pss + sa * sa) % kMod;  // (-pa + (pa + 1)) * sa * sa85      spp = (spp + sa * (-pa * pa + (pa + 1) * (pa + 1))) % kMod;86      pp = (pp - pa * pa + (pa + 1) * (pa + 1)) % kMod;87      ps = (ps + sa) % kMod;  // (-pa + (pa + 1)) * sa88 89      ++p[a];90    }91 92    return (ans + kMod) % kMod;93  }94 95 private:96  static constexpr int kMod = 1'000'000'007;97 98  // Returns C(n, 2)99  long nC2(long n) {100    return n * (n - 1) / 2 % kMod;101  }102};103