As a solution to this problem, there exists the following simple algorithm (though it will result in TLE):

• Define \(d_k[x]\) as “the product of \(A_i\) for all integers \(1\le i\le k\) satisfying \(A_i = x\).”
• Updating from \(d_{k-1}[x]\) to \(d_k[x]\) can be done in \(O(1)\) time by updating in-place.
• The answer for the case \(k=k_0\) is \(\displaystyle \prod_{x\subset A_{k_0}} d[x]\). This value can be calculated in \(O\left(2^{\mathrm{popcount}\left(A_{k_0}\right)}\right)\) time.

However, the time complexity of this algorithm is \(\Theta(N \max A)\) in the worst case, resulting in TLE. Let’s consider improving this algorithm.

For \(0\le p,q < 2^{10}\), let \((p,q)=2^{10}p+q\). Note that integers \(x\) satisfying \(0\le x < 2^{20}\) and pairs of integers \((p,q)\) satisfying \(0\le p,q < 2^{10}\) correspond one-to-one through the above mapping. Hereafter, we will treat them as identical. Also, let \(A_k=(P_k,Q_k)\) where we define \(P_k,Q_k\), and let \(1_{[\text{cond}]}\) be a function that returns \(1\) if \(\text{cond}\) is true and \(0\) if false.

Furthermore, we denote the condition \(x\ \mathrm{OR}\ y = y\) as \(x \subset y\).

For \(0\le p,q < 2^{10}\), define \(\displaystyle d_k[(p,q)]=\prod_{1\le i\le k} A_i^{1_{[P_i \subset p \land Q_i = q]}}\). The initial value is \(d_0[(p,q)]=1\).

With this definition of \(d\), updating \(d\) and calculating the answer can be done as follows:

Updating from \(d_{k-1}\) to \(d_k\)

After updating \(d_k\) in-place with \(d_{k-1}\), multiply \(A_k\) to \(d_k[(p,Q_k)]\) for \(p \supset P_k\).

Calculating the answer

Transform the answer \(\displaystyle \prod_{\substack{1\le i\le k\\ A_i \subset A_k} }A_i\) step by step.

\[ \begin{aligned} &\phantom{=} \prod_{\substack{1\le i\le k\\ A_i \subset A_k} }A_i\\ &= \prod_{1\le i\le k} A_i^{1_{[P_i \subset P_k \land Q_i \subset Q_k]}} \\ &=\prod_{q \subset Q_k} \prod_{1\le i\le k} A_i^{1_{[P_i \subset P_k \land Q_i =q]}} \\ &= \prod_{q\subset Q_k} d_k[(P_k , q)] \end{aligned} \]

Therefore, \(\displaystyle \prod_{q\subset Q_k} d_k[(P_k , q)]\) is the answer.

Both updating from \(d_{k-1}\) to \(d_k\) and calculating the answer can be done with \(\sqrt{\max A}=2^{10}\) calculations. Therefore, the overall time complexity is \(O(N\sqrt{\max A})\).

By implementing this appropriately, we can solve this problem.

Implementation Example (Python3)

n = int(input())
INF = 1 << 10
MOD = 998244353
d = [1] * (1 << 20)
ans = [0] * n
cnt = 0
for x in list(map(int, input().split())):
    x1, x2 = x >> 10, x & (INF - 1)
    for i in range(INF):
        if (x1 & i) == x1:
            d[(i << 10) | x2] = x * d[(i << 10) | x2] % MOD
    res = 1
    for i in range(INF):
        if (x2 & i) == i:
            res = res * d[(x1 << 10) | i] % MOD
    ans[cnt] = res
    cnt += 1
print(*ans, sep="\n")