問題一覧 > 通常問題

No.1492 01文字列と転倒

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 100
作問者 : penguinmanpenguinman / テスター : kaagekaage shotoyooshotoyoo
12 ProblemId : 6188 / 出題時の順位表
問題文最終更新日: 2021-04-25 00:56:27

問題文

0, 1 のみからなる文字列 $S$ のうち、以下の操作を繰り返すことで空文字列にできるものを 良い文字列 と定義します。

  • $S_i=$0$,\ S_{i+1}=$1$\ (1\leq i\lt|S|)$ を満たす $i$ を選び、$S_i$ と $S_{i+1}$ を削除する。

長さ $2N$ の 良い文字列 のうち、転倒数が $K$ であるものはいくつありますか?

$K=0,\ 1,\ldots,\ N^2$ についてこの問題を解き、それぞれの答えを与えられる素数 $M$ で割った余りを出力してください。

01文字列 $S$ の転倒数とは、$S_i=$1, $S_j=$0 を満たす $(i,\ j)$ の組 $(1\leq i\lt j\leq |S|)$ の個数のことを指します。

入力

\(N\) \(M\)

  • $1\leq N\leq 100$
  • $10^8\leq M\leq 10^9+7$
  • $M$ は素数
  • 入力は全て整数

出力

$N^2+1$ 行に渡って出力してください。

$i$ 行目には $K=i-1$ における答えを $M$ で割った余りを出力してください。

サンプル

サンプル1
入力
2 998244353
出力
1
1
0
0
0

長さ $2N$ の 良い文字列0011, 0101 の $2$ つです。それぞれの転倒数は $0,\ 1$ であるためこのような出力になります。

サンプル2
入力
4 1000000007
出力
1
1
2
3
3
3
1
0
0
0
0
0
0
0
0
0
0

余談ですが、長さ $2N$ の 良い文字列 の転倒数は必ず $N^2$ 以下に収まります。

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