201345: [AtCoder]ARC134 F - Flipping Coins

Memory Limit：1024 MB Time Limit：5 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $1000$ points

Problem Statement

There are $N$ coins numbered $1, 2, \ldots, N$ arranged in a row. Initially, all coins face up.

Snuke chooses a permutation $p$ of $(1,\ldots,N)$ with equal probability, and do $N$ operations. The $i$-th operation does the following.

  • If the coin numbered $i$ faces down, do nothing.
  • If the coin numbered $i$ faces up, turn that coin over and then turn over the coin numbered $p_i$.

After the $N$ operations, Snuke will receive $W^k$ yen (Japanese currency) from his mother, where $k$ is the number of coins facing up.

Find the expected value of the amount Snuke will get, multiplied by $N!$ (it can be proved that this is an integer), modulo $998244353$.

Constraints

  • All values in input are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq W < 998244353$

Input

Input is given from Standard Input in the following format:

$N$ $W$

Output

Print the expected value of the amount Snuke will get, multiplied by $N!$, modulo $998244353$.

Sample Input 1

4 2

Sample Output 1

90
  • When $p=(1,4,2,3)$, the operations go as follows.
    • In the $1$-st operation, the coin numbered $1$ faces down, and then the coin numbered $1$ faces up.
    • In the $2$-nd operation, the coin numbered $2$ faces down, and then the coin numbered $4$ faces down.
    • In the $3$-rd operation, the coin numbered $3$ faces down, and then the coin numbered $2$ faces up.
    • In the $4$-th operation, nothing is done.
  • In the end, two coins face up, so he receives $4$ yen.

Sample Input 2

2 100

Sample Output 2

10001

Sample Input 3

200000 12345

Sample Output 3

541410753
  • Be sure to find the value modulo $998244353$.

Input

题意翻译

给定一排 $n$ 枚硬币，初始时所有硬币正面向上。 Snuke 会等概率地选择一个长度为 $n$ 的排列 $p = (p_1, p_2, \dots, p_n)$，并执行 $n$ 次操作。第 $i$ 次操作会执行如下步骤： - 若第 $i$ 枚硬币是反面朝上的，什么也不做。 - 若第 $i$ 枚硬币是正面朝上的，翻转它，并翻转第 $p_i$ 枚硬币。 给定 $w$。设 $n$ 次操作完后正面朝上的硬币数为 $k$，则这排列的贡献即为 $w^k$。 你需要求出这贡献的期望值乘 $n!$ 后在模 $998244353$ 意义下的值。容易证明这值定是整数。 $1\le n\le 2\times 10^5, \ 1\le w < 998244353$。

Source/Category

加入题单

算法标签：