問題一覧 > 通常問題

No.2904 Distinct Multisets in a Way

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 29
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru cleantted 👑 Nachia
お気に入りにしたユーザー ProblemId : 10908 / 自分の提出
問題文最終更新日: 2024-09-26 23:01:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 448 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。