{"problem":{"name":"Colorful Candies 2","description":{"content":"There are $N$ candies arranged in a row from left to right.   Each candy has one of the following $10^9$ colors: Color $1$, Color $2$, $\\ldots$, Color $10^9$.   For each $i = 1, 2, \\ldots, N$, the $i$","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc215_g"},"statements":[{"statement_type":"Markdown","content":"There are $N$ candies arranged in a row from left to right.  \nEach candy has one of the following $10^9$ colors: Color $1$, Color $2$, $\\ldots$, Color $10^9$.  \nFor each $i = 1, 2, \\ldots, N$, the $i$\\-th candy from the left has Color $c_i$.\nTakahashi will choose $K$ from the $N$ candies and get those $K$ candies.  \nThere are $\\binom{N}{K}$ ways to choose $K$ from the $N$ candies, where $\\binom{N}{K}$ is a binomial coefficient. Takahashi will randomly select one of these $\\binom{N}{K}$ ways with equal probability.\nBecause Takahashi wants to eat colorful candies, the more variety of colors his candies have, the happier he will be.  \nFor each scenario $K = 1, 2, \\ldots, N$, find the expected value of the number of different colors Takahashi's candies will have.  \nWe can prove that the sought value is a rational number. Print this rational number modulo $998244353$, as described in Notes.\n\n## Constraints\n\n*   $1 \\leq N \\leq 5 \\times 10^4$\n*   $1 \\leq c_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$c_1$ $c_2$ $\\ldots$ $c_N$\n\n[samples]\n\n## Notes\n\nWhen you print a rational number, first write it as a fraction $\\frac{y}{x}$, where $x, y$ are integers and $x$ is not divisible by $998244353$ (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer $z$ between $0$ and $P - 1$, inclusive, that satisfies $xz \\equiv y \\pmod{998244353}$.","is_translate":false,"language":"English"}],"meta":{"iden":"abc215_g","tags":[],"sample_group":[["3\n1 2 2","1\n665496237\n2\n\nWhen $K = 1$, he will get the $1$\\-st candy, $2$\\-nd candy, or $3$\\-rd candy. In any case, his candy will have one color, so the expected value of the number of different colors is $1$.\nWhen $K = 2$, he will get the $1$\\-st and $2$\\-nd candies, $2$\\-nd and $3$\\-rd candies, or $1$\\-st and $3$\\-rd candies.\n\n*   If he gets the $1$\\-st and $2$\\-nd candies, they have two different colors.\n*   If he gets the $2$\\-nd and $3$\\-rd candies, they have one color.\n*   If he gets the $1$\\-st and $3$\\-rd candies, they have two different colors.\n\nThus, the expected value of the number of different colors is $\\frac{1}{3} \\cdot 2 + \\frac{1}{3} \\cdot 1 + \\frac{1}{3} \\cdot 2 = \\frac{5}{3}$.  \nBe sure to print it modulo $998244353$ as described in Notes.\nWhen $K = 3$, he will always get the $1$\\-st, $2$\\-nd, and $3$\\-rd candies, which have two different colors, so the expected value of the number of different colors is $2$."],["11\n3 1 4 1 5 9 2 6 5 3 5","1\n725995895\n532396991\n768345657\n786495555\n937744700\n574746754\n48399732\n707846002\n907494873\n7"]],"created_at":"2026-03-03 11:01:13"}}