Dice

AtCoder

IDfps_24_q

Time4000ms

Memory256MB

Difficulty—

There are two dice, called die $1$ and die $2$. * Die $1$ is an $N$\-sided die, where each side shows a distinct positive integer $A_1, A_2, \dots, A_N$ with equal probability. * Die $2$ is an $M$\-sided die, where each side shows a distinct positive integer $B_1, B_2, \dots, B_M$ with equal probability. You are also given a positive integer $K$. For each $k = 1, 2, \dots, K$, solve the following problem: * When rolling die $1$ and die $2$ simultaneously, compute the expected value of $(\text{sum of the outcomes})^k$ modulo $998244353$. What does expected value modulo $998244353$ mean? It can be proven that the expected value is always a rational number. Under the constraints of this problem, if the value can be expressed as $\tfrac{P}{Q}$ with coprime integers $P$ and $Q$, then there exists a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353}$ and $0 \leq R < 998244353$. You are asked to compute this $R$. ## Constraints * $1 \leq N \leq 10^5$ * $1 \leq M \leq 10^5$ * $1 \leq K \leq 10^5$ * $1 \leq A_1 < A_2 < \dots < A_N \leq 10^8$ * $1 \leq B_1 < B_2 < \dots < B_M \leq 10^8$ * All input values are integers ## Input The input is given from standard input in the following format: $N$ $M$ $K$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_M$ [samples]

Samples

Input #1

3 2 3
1 2 3
4 5

Output #1

499122183
166374102
499122469

For example, if die $1$ shows $3$ and die $2$ shows $5$, then the cube of the sum is $(3+5)^3 = 512$.

Input #2

8 9 5
26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081
12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Dice",
    "description": {
      "content": "There are two dice, called die $1$ and die $2$. *   Die $1$ is an $N$\\-sided die, where each side shows a distinct positive integer $A_1, A_2, \\dots, A_N$ with equal probability. *   Die $2$ is an $M",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_q"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are two dice, called die $1$ and die $2$.\n\n*   Die $1$ is an $N$\\-sided die, where each side shows a distinct positive integer $A_1, A_2, \\dots, A_N$ with equal probability.\n*   Die $2$ is an $M...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments