Subset Product Problem

AtCoder

IDarc205_e

Time6000ms

Memory256MB

Difficulty—

You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\ldots,A_N)$. For $k=1,2,\ldots,N$, solve the following problem. * Find the **product**, modulo $998244353$, of $A_i$ for all integers $i$ between $1$ and $k$, inclusive, such that the bitwise $\mathrm{OR}$ operation of $A_i$ and $A_k$ equals $A_k$. What is bitwise $\mathrm{OR}$ operation?The bitwise $\mathrm{OR}$ of non-negative integers $X$ and $Y$, denoted $X\ \mathrm{OR}\ Y$, is defined as follows. * When $X\ \mathrm{OR}\ Y$ is written in binary, the digit at the $2^k$ $(k \geq 0)$ place is $1$ if at least one of the digits at the $2^k$ place when $X$ and $Y$ are written in binary is $1$, and $0$ otherwise. For example, $3\ \mathrm{OR}\ 5 = 7$ (in binary: $011\ \mathrm{OR}\ 101 = 111$). ## Constraints * $1\le N\le 4\times 10^5$ * $0\le A_i < 2^{20}$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $A_2$ $\ldots$ $A_N$ [samples]

Samples

Input #1

4
1 2 3 5

Output #1

1
2
6
5

*   When $k=1$: For $i=1$, the bitwise $\mathrm{OR}$ operation of $A_i$ and $A_k$ is $1$. Therefore, the answer for the case $k=1$ is $A_1=1$.
*   When $k=2$: For $i=1,2$, the bitwise $\mathrm{OR}$ operation of $A_i$ and $A_k$ is $3,2$, respectively. Therefore, the answer for the case $k=2$ is $A_2=2$.
*   When $k=3$: For $i=1,2,3$, the bitwise $\mathrm{OR}$ operation of $A_i$ and $A_k$ is all $3$. Therefore, the answer for the case $k=3$ is $A_1\times A_2\times A_3=6$.
*   When $k=4$: For $i=1,2,3,4$, the bitwise $\mathrm{OR}$ operation of $A_i$ and $A_k$ is $5,7,7,5$, respectively. Therefore, the answer for the case $k=4$ is $A_1\times A_4=5$.

Input #2

9
3 1 4 1 5 9 2 6 5

Output #2

Input #3

12
437926 528156 284664 1038330 692060 720863 602077 1027766 868190 532252 982711 876446

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Subset Product Problem",
    "description": {
      "content": "You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\\ldots,A_N)$. For $k=1,2,\\ldots,N$, solve the following problem. *   Find the **product**, modulo $998244353$, of $A_i$ for al",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc205_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a length-$N$ sequence of non-negative integers $A=(A_1,A_2,\\ldots,A_N)$.\nFor $k=1,2,\\ldots,N$, solve the following problem.\n\n*   Find the **product**, modulo $998244353$, of $A_i$ for al...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments