No.2904 Distinct Multisets in a Way
タグ : / 解いたユーザー数 29
作問者 : 👑
amentorimaru
cleantted
👑
Nachia
Problem Statement
In this problem, a multiset with $K$ elements $e_1,e_2,e_3,\ldots,e_{K}$ is denoted by $\{\!|e_1,e_2,e_3,\ldots,e_{K}|\!\}$.
Consider the operation of taking $1$ element from a multiset $S$ so that each element is taken with probability $1/|S|$.
For a pair $(S_1,S_2)$ of $2$ non-empty multisets, let $P(S_1,S_2)$ be the probability distribution of the sum of the elements taken by performing this operation $1$ time each on $S_1$ and $S_2$, independently.
Find the number, modulo $998244353$, of pairs $(S_1,S_2)$ of $2$ multisets satisfying all of the following conditions. Here, $(S_1,S_2)=(S_2,S_1)$ are regarded as identical.
- $|S_1|=|S_2|=2^N$
- All elements of $S_1$ and $S_2$ are positive integers.
- $(S_1,S_2)\neq (\{\!|1,2,3,\ldots,2^N|\!\},\ \{\!|1,2,3,\ldots,2^N|\!\})$
- $P(S_1,S_2)=P(\{\!|1,2,3,\ldots,2^N|\!\},\ \{\!|1,2,3,\ldots,2^N|\!\})$
Input
$N$
- All input values are integers.
- $0\leq N\leq 5\times 10^5$
Output
Print the number of pairs modulo $998244353$, followed by a newline.
Sample
Sample 1
Input
3
Output
3
We have $2^3=8$.
The following $3$ pairs satisfy the conditions: $(\{\!|1,2,2,3,3,4,4,5|\!\},\ \{\!|1,3,5,5,7,7,9,11|\!\}),\ (\{\!|1,2,3,3,4,4,5,6|\!\},\ \{\!|1,2,5,5,6,6,9,10|\!\}),\ (\{\!|1,2,2,3,5,6,6,7|\!\},\ \{\!|1,3,3,5,5,7,7,9|\!\})$.
For all of these pairs, $P$ is the probability distribution that takes the value $2$ with probability $1/64$, $3$ with probability $1/32$, $4$ with probability $3/64$, $5$ with probability $1/16$, $6$ with probability $5/64$, $7$ with probability $3/32$, $8$ with probability $7/64$, $9$ with probability $1/8$, $10$ with probability $7/64$, $11$ with probability $3/32$, $12$ with probability $5/64$, $13$ with probability $1/16$, $14$ with probability $3/64$, $15$ with probability $1/32$, and $16$ with probability $1/64$.
This distribution coincides with $P(\{\!|1,2,3,4,5,6,7,8|\!\},\ \{\!|1,2,3,4,5,6,7,8|\!\})$.
As an example, let us verify the probability that the sum of the elements is $4$ for the pair $(\{\!|1,2,2,3,3,4,4,5|\!\},\ \{\!|1,3,5,5,7,7,9,11|\!\})$.
For verification, relabel the numbers as $(\{1,2_1,2_2,3_1,3_2,4_1,4_2,5\},\ \{1',3',5'_1,5'_2,7'_1,7'_2,9',11'\})$. Then the ways of taking elements whose sum is $4$ are the $3$ ways $(1,3'),\ (3_1,1'),\ (3_2,1')$, so the sum is indeed $4$ with probability $3/64$.
Sample 2
Input
500000
Output
329966357
Find the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。