Update 2 — Thanks adamant for his Subset convolution interpretation blog. It does simplifies a lot of things.
Update 1 -
Let's consider this problem -
We have a function subset_convolution(A,B)
it gives us Subset Sum Convolution of two sets $$$A, B$$$.
Let's say we array $$$A$$$ with $$$A[0]=1$$$ and we want to find A^K
defined as $$$A$$$ convoluted with itself $$$K$$$ times.
A^2 = subset_convolution(A,A)
A^3 = subset_convolution(A^2,A)
...
A^k = subset_convolution(A^{k-1},A)
The best I can think right now is using something on lines of fast exponential to achieve $$$O(log K*N^2*2^N)$$$ time where $$$2^N$$$ is the size of A. Also, there exist some solutions $$$O(N^3*2^N)$$$ using the fact that the majority of the multiplications will be with A[0] and permutations & combinations.
But it can be done in $$$O(N^2*2^N)$$$ using tricks well known at some places. Idk why it works tho.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
TLDR — Just me rambling about the old ARC problem I was solving for the last 3 days. Something "set power series" similar to "power series for polynomials" I came across and I have an iota idea about it right now. Also amplifying some unanswered bugaboo related to it in the discussion of that ARC round. Spoiler is just very very briefly mention different solutions I had for ARC105F problem.
Me trying to solve ARC105 FI vced ARC 105. Then while upsolving/reading the editorial of F — Lights Out on Connected Graph along with comments on discussion page. I came across a non trivial solution to that problem by Elegia under the view of "set power series".
It took me multiple readings of atcoder editorial to come up with one $$$O(2^n*m+n*3^n)$$$ soln then I was able to verify equations mentioned along with defined logarithm (by sheaf) of 'set power series' would indeed give a correct solution for this problem. But it's too slow here.
At first, I tried doing some minor optimisations to pass it since it just had an extra "n" factor compared to intended time complexity and "n" was just 17 here. Nothing worked out. The next day I optimised that subset convolution and came up with an $$$O(2^n*m+n^4*2^n)$$$ soln I was expecting an AC since it should be faster than the previous soln. But again TLE. Later I looked at some redundant calculation in that subset convolution solution and was able to optimise it to get one $$$O(2^n*m+n^3*2^n)$$$ soln. It barely gets an AC.
Then I looked at the fastest solution to that problem and came across maroonrk's submission of that problem. I was counting ordered partitions in that logarithm and dividing by $$$|P|!$$$, while counting them as unordered would remove that extra "n". One more day, I had $$$O(2^n*m+3^n)$$$ soln (the one mentioned in editorial) and $$$O(2^n*m+n^2*2^n)$$$ soln (the one mentioned by Elegia).
So I now have 5 different solutions for this problem but the story doesn't end here especially because of dario2994's and mmaxio's comments.
The logarithm of 'set power series' is a function $$$g(x)=\sum_{S} g_{S} x^{S}$$$ such that $$$f(x) = \sum_{S} (\sum_{\mathcal{P}} \prod_{P_i \in \mathcal{P}} g_{P_i}) x^{S}$$$, where the inner summation goes over all unordered partitions $$$P$$$ of $$$S$$$.
dario2994 submission on the same problem implements a small library for subsets with functions namely and/or/xor/subset convolutions along with log and exp of set power series.
(First to answer dario2994 comment — Yes, there does exist a clever way (and maroonrk's submission) to compute subset convolution.)
I did asked some of my friends and seniors doing MATH major — where can I read formal definitions of "set power series" since googling it just gave me useless results and none of them ever heard it.
Q1 — What exactly is the definition of exp of set power series? (One implemented by dario2994 and mentioned by mmaxio). Where can I read about more similar definitions?
mmaxio mentions Lu Kaifeng's report, googling about his report along with keywords such as "set power series" doesn't yield helpful results. But then I came across this blog. It has a code snippet and mentions For details, please refer to the 2015 Proceedings of the National Training Team Lu Kaifeng, "The Properties and Application of Set Power Series and Its Fast Algorithm"
.
It's a 17 page report published in 2015 in Chinese, I wasn't able to find an English version. Hence must be a well-known problem in China and hence a "trivial solution" by Elegia. I tried auto translating it using the method mentioned by z4120 in Auto-translated Chinese national IOI training team report papers but I messed up a step somewhere and ended up with just Chinese translated into Chinese, would really appreciate it if someone can translate it for me.
Q2 — mmaxio's comment looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently
makes me much more interested in this. It opens the door to a hell of a lot of possibilities here (a reason for this blog here) integration, derivative, inverse, square root to name some among similar operations on polynomials and series.
I do remember the day when I learnt about the inverse and square root of a polynomial and was overwhelmed by it. On that day, I just concluded that "polynomials are just numbers". Later I have seen some problems which even used dp states as polynomials instead of integers. The observation "polynomials are just numbers" makes it easy for me to understand those editorials and those problems do excite me these days. Something similar for sets will for sure generalize it further.
Publishing this blog with the expectation that I would find more material to read about it since Google isn't my friend here.
Update 1 (solution) —
O(N^2*2^N) solution of initial problemJust like polynomials exp(K*log(A))
simply works here. Don't ask me why because that's the whole point of this blog.
Proof by AC