問題一覧 > 通常問題

No.770 Median Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : PulmnPulmn
3 ProblemId : 2475 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-12-17 22:57:03

問題文

次の条件を満たす長さ $N$ の整数列 $A$ の通り数を求めてください。ただし、この値は非常に大きくなる場合があるので $10^9+7$ で割った時の余りを出力してください。

条件:以下の式を満たすような長さ $N$ の $1$ 以上 $N$ 以下の整数列 $B$ が存在する。ただし、$med(x,y,z)$ は $3$ つの値 $\{x,y,z\}$ の中央値を表す。

$A_1=med(1,B_1,N)$
$A_2=med(med(1,B_1,N-1),B_2,N)$
$A_3=med(med(med(1,B_1,N-2),B_2,N-1),B_3,N)$
 $\vdots$
$A_i=med(med(med(\dots med(\dots med(med(1,B_1,N-i+1),B_2,N-i+2),\dots ,B_j,N-i+j)\dots ),B_{i-1},N-1),B_i,N)$
 $\vdots$
$A_N=med(med(med(\dots med(\dots med(med(1,B_1,1),B_2,2),\dots ,B_j,j)\dots ),B_{N-1},N-1),B_N,N)$

※サンプルを参考にしてください

入力

$N$

$1\le N\le 3,000$

出力

条件を満たす整数列 $A$ の通り数を $10^9+7$ で割った時の余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
6
出力
1448

例えば $A=(1,2,6,5,4,6)$ は $B=(1,2,6,3,1,6)$ とすると、次の式を満たすので条件を満たします。
$A_1=med(1,B_1,6)$
$A_2=med(med(1,B_1,5),B_2,6)$
$A_3=med(med(med(1,B_1,4),B_2,5),B_3,6)$
$A_4=med(med(med(med(1,B_1,3),B_2,4),B_3,5),B_4,6)$
$A_5=med(med(med(med(med(1,B_1,2),B_2,3),B_3,4),B_4,5),B_5,6)$
$A_6=med(med(med(med(med(med(1,B_1,1),B_2,2),B_3,3),B_4,4),B_5,5),B_6,6)$

サンプル2
入力
1
出力
1

サンプル3
入力
100
出力
328638438

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