D - AND OR Equation Editorial by evima
[1] Remodeling the problem with sets
Let the integers from \(0\) to \(2^N-1\) correspond to the subsets of \(S = \{0, 1, \ldots, N - 1\}\) by seeing them as binary sequences. The problem will be rephrased into the following, where \(2^S\) denotes the set of the subsets of \(S\):
Count maps \(f\colon 2^S\longrightarrow \{0,1,\ldots,K\}\) such that:
- \(f(A)+f(B)=f(A\cap B)+f(A\cup B)\) for all \(A, B\in 2^S\).
[2] Characterization
We can prove the following:
Assume that \(f\colon 2^S\longrightarrow \mathbb{Z}\) satisfies \(f(A)+f(B)=f(A\cap B)+f(A\cup B)\) for all \(A, B\in 2^S\). Then, \(f(A) = c + \sum_{i\in A}x_i\) holds for all \(A \in 2^S\), where \(c = f(\emptyset)\) and \(x_i = f\bigl(\{i\}\bigr) - c\) (\(0\leq i<N\)).
Let us prove this. If we define \(g\colon 2^S\longrightarrow \mathbb{Z}\) by \(g(A) = f(A) - c\), the following holds:
- \(g(\emptyset) = 0\).
- \(g(A)+g(B)=g(A\cap B) + g(A\cup B)\) for all \(A,B\in 2^S\).
- \(g\bigl(\{i\}\bigr) = x_i\).
Additionally, it follows from 1. and 2. that \(g(A)+g(B) = g(A\cup B)\) if \(A\cap B = \emptyset\). By this property, it holds that:
\[g(A) = g\biggl(\bigcup_{i\in A}\{i\}\biggr) = \sum_{i\in A}g\bigl(\{i\}\bigr) = \sum_{i\in A} x_i,\]
which shows \(f(A) = c + \sum_{i\in A}x_i\).
On the other hand, the following also holds:
If \(f\colon 2^S\longrightarrow \mathbb{Z}\) is defined by \(f(A) = c + \sum_{i\in A}x_i\) for \(c, x_0,\ldots, x_{N-1}\in \mathbb{Z}\), then \(f(A)+f(B)=f(A\cap B)+f(A\cup B)\) holds for all \(A, B\in 2^S\).
One can easily prove this by separately considering the contribution of \(c\) and each \(x_i\) on both sides.
[3] Remodeling the problem again
By [2], the counting problem can again be rephrased into the following:
Count tuples of integers \((c, x_0, x_1, \ldots, x_{N-1})\) such that: \(0\leq c + \sum_{i\in A}x_i\leq K\) for all \(A\in 2^S\).
If we denote by \(s^{-}\) the sum of \(x_i\) over all \(i\) such that \(x_i < 0\), and by \(s^{+}\) the sum of \(x_i\) over all \(i\) such that \(x_i > 0\), the above inequality can be transformed into \(0\leq c + s^{-}\) and \(c + s^{+}\leq K\), that is, \(-s^{-}\leq c\leq K - s^+\). There are \(\max\{0, K + 1 - s^+ + s^-\}\) such values for \(c\).
Since \(s^+ - s^- = \sum_{i} \lvert x_i\rvert\), our problem is now:
Find the sum of \((1+K-\sum_{i}\lvert x_i\rvert)\) over all tuples of integers \((x_0, \ldots, x_{N-1})\) such that \(\sum_i\lvert x_i\rvert \leq K\).
[4] Computing the answer.
We will explain two methods.
Method 1
Let us first fix the number \(n\) of indices \(i\) such that \(x_i \neq 0\) and then do the count. There are \(\binom{N}{n}\) ways to choose \(i\)’s, and \(2^n\) ways to choose their signs. We should multiply these by:
- the sum of \((1+K-\sum_{i}x_i)\) over all tuples of positive integers \((x_1,\ldots, x_n)\) such that \(\sum_i x_i \leq K\).
This is equal to the following counts:
- The number of tuples of positive integers \((a, x_1,\ldots, x_n)\) such that \(a + \sum x_i \leq K + 1\).
- The number of tuples of positive integers \((a, b, x_1,\ldots, x_n)\) such that \(a + b + \sum x_i = K + 2\).
These counts equal \(\binom{K+1}{n+1}\), so the answer is:
\[\sum_{n=0}^N 2^n\binom{N}{n}\binom{K+1}{n+1}.\]
Method 2
Let \(a_n\) be the number of tuples of integers \((x_1, \ldots, x_N)\) such that \((x_1, \ldots, x_N)\). Consider the generating function \(f(x) = \sum_{n=0}^{\infty} a_nx^n\) of \(a_n\), which is:
\[f(x) = (1+2x+2x^2+2x^3+\cdots)^N = \biggl(\frac{1+x}{1-x}\biggr)^N = \frac{(1+x)^N}{(1-x)^N}.\]
The answer is \((K+1)a_0 + Ka_1 + \cdots + 1\cdot a_K\), which can be represented as \([x^{K}]f(x)g(x)\) using \(g(x) = 1 + 2x + 3x^2 + \cdots = (1-x)^{-2}\). Thus, the answer is \([x^K]\frac{(1+x)^N}{(1-x)^{N+2}}\).
If we represent the numerator as \(\bigl((1-x)+2x\bigr)^N\), the binomial expansion leads to the formula we obtained in Method 1. Alternatively, a direct binomial expansion of the numerator shows that the answer is:
\[\sum_{n=0}^N\binom{N}{n}\binom{K-n+N+1}{N+1},\]
which can also be computed.
In either case, the answer can be found in \(O(N)\) time by efficiently computing the required binomial coefficients (for example, one can compute the ratio between their values for respective \(n\)’s, or use a data structure that can handle range products).
posted:
last update: