https://atcoder.jp/contests/abc290/tasks/abc290_e

We have a variation of this, find sum of $$$F(x)$$$ for every subsequence of a string, and should be better than $$$O(N^2)$$$.

I can only think of $$$O(N^2)$$$ approach which involves finding individual contribution of every unequal pair of characters, can we optimize this?

Let's stick to only odd-length subsets for simplicity, given an array of integers, find sum of median of all subsets mod $$$1e9 + 7$$$, median is the middle element for odd-length subsets when sorted.

First step would obviously be sorting but then to count number of subsets whose median is $$$arr[i]$$$ we need to find number of ways to pick equal number of elements from it's left and right, if left has $$$x$$$ elements and right has $$$y$$$ elements, then,

Finding this for each element would make it $$$O(N^2)$$$, is there a faster method to find the sum of binomial coefficients as shown above efficiently possibly with some precomputation? Or some entirely different approach to solve the original problem?

How would we implement a multiset data structure that allows insertion, deletion and querying GCD of values currently present in multiset?

insert(5)
GCD() -> 5
insert(10)
GCD() -> 5
remove(5)
GCD() -> 10

This question is not from some existing problem and was just wondering if it was possible to have such data structure where deletion is possible on operations like GCD. I believe this would be helpful https://cp-algorithms.com/data_structures/deleting_in_log_n.html but can't understand how we would apply this or maybe some other method which would work for large numbers upto 1e18.

Suppose we're given an array of length N upto 1e6 and we apply prefix sum to the array in place, ie. [a, b, c] becomes [a, a + b, a + b + c], we repeat this K times where K can be upto 1e6.

Can we find the resulting array after K operations faster than O(N*K)?

I have observed each preceding element has some contribution for an element in resulting array, but the coefficient doesn't seem intuitive to derive, can someone help derive how to compute the resulting array?

Finding a particular element of the resulting array, for example, just last element in better than O(N*K) would also suffice, hope someone can help.