問題一覧 > 通常問題

No.2872 Depth of the Parentheses

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 93
作問者 : 寝癖 / テスター : yuusaan 👑 seekworser
お気に入りにしたユーザー ProblemId : 10787 / 自分の提出
問題文最終更新日: 2024-09-09 08:51:43
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 444 (順位表) の他の問題:

Problem Statement

Neguse-kun has a coin that lands heads with probability $x\%$ and tails with probability $(100-x)\%$, and an empty string $S$.
Now, consider repeating the following trial $2K$ times.

Toss the coin, and

  • if it lands heads, append ( to the end of $S$.
  • if it lands tails, append ) to the end of $S$.

For the parentheses sequence $S$ of length $2K$ obtained in this way, find the expected value of its depth, ${\rm mod}\ 998244353$.


Here, the depth of a parentheses sequence $S$ is the value defined as follows.
For the string $T_i$ consisting of the first $i$ characters of $S$, consider appending ) to the end of $T_i$ to make it a correct parentheses sequence, and let $D_i$ be the minimum number of ) required. Then the depth is:

  • $\displaystyle\max_{1\le i\le 2K}D_i$ if $S$ is a correct parentheses sequence.
  • $0$ otherwise.
For example, the depth of (())() is $2$, the depth of () is $1$, and the depth of ((()))(( is $0$ (it is not a correct parentheses sequence).

What is the expected value ${\rm mod}\ 998244353$?

It can be proved that the expected value to be found is always a rational number. Moreover, under the constraints of this problem, it is guaranteed that when the expected value is expressed as an irreducible fraction $\frac{p}{q}$, $q$ is not divisible by $998244353$. In this case, there exists exactly one $0\le r < 998244353$ satisfying $p=qr\ ({\rm mod}\ 998244353)$, so output this $r$.


What is a correct parentheses sequence?

A correct parentheses sequence is a non-empty string that satisfies one of the following.

  • ()
  • A string obtained by concatenating $S,T$ in this order, for some correct parentheses sequences $S,T$
  • A string obtained by concatenating (,$S$,) in this order, for some correct parentheses sequence $S$

Input

The input is given from standard input in the following format. 
$x\ K$

  • $0\le x\le 100$
  • $1\le K \le 10$
  • All inputs are integers.

This problem includes high-difficulty constraints as evil cases, which do not affect the AC verdict. If you have the energy to spare, please give them a try. The constraints of the evil cases are as follows.

Constraints of the evil cases
  • $0\le x\le 100$
  • $1\le K \le 10000$
  • All inputs are integers.
If you are not attempting the evil cases, having your program terminate immediately when the input does not satisfy the normal constraints will make the judging finish sooner.

Output

Output the answer in 1 line.

Sample

Sample 1
Input
50 2
Output
811073537

The parentheses sequences obtained and their probabilities are as follows.

  • With probability $\frac{1}{16}$, (())
  • With probability $\frac{1}{16}$, ()()
  • With probability $\frac{7}{8}$, not a correct parentheses sequence
Therefore, the expected value to be found is $\frac{1}{16}\times2 + \frac{1}{16}\times 1 + \frac{7}{8}\times 0=\frac{3}{16}$.

Sample 2
Input
100 5
Output
0

The probability that the obtained parentheses sequence is a correct parentheses sequence is $0$.

Sample 3
Input
31 4
Output
414773523

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。