No.1785 Inequality Signs

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 61
作問者 :

8UqsVg4r / テスター :

NatsubiSogan

7 ProblemId : 7404 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-12-13 23:58:03

$<, \leq$ のいずれかからなる長さ $N - 1$ の不等号列 $I = ({ieq}_{1}, {ieq}_{2}, \dots, {ieq}_{N - 1})$ に対して、スコア を以下のように定義します。

整数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ であって、 $1 \leq A_{1} {ieq}_{1} A_{2} {ieq}_{2} A_{3} \dots A_{N - 1} {ieq}_{N - 1} A_{N} \leq K$ を満たすものの数。

列 $I$ として考えられるものは $2^{N - 1}$ 通りありますが、それらすべてについてスコアを求め、その総和を $10^{9} + 7$ で割ったあまりを出力してください。

 $N K$

求めた答えを $10^{9} + 7$ で割ったあまりを $1$ 行に出力してください。

最後に改行してください。

3 2

${ieq}_{1}$ が $<$ で ${ieq}_{2}$ が $<$ のとき：条件を満たす $A$ は存在しません。
${ieq}_{1}$ が $\leq$ で ${ieq}_{2}$ が $<$ のとき： $A = (1, 1, 2)$ のみが条件を満たします。
${ieq}_{1}$ が $<$ で ${ieq}_{2}$ が $\leq$ のとき： $A = (1, 2, 2)$ のみが条件を満たします。
${ieq}_{1}$ が $\leq$ で ${ieq}_{2}$ が $\leq$ のとき： $A = (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2)$ の $4$ つが条件を満たします。

これらを合計した $6$ が出力する値となります。

31415 92653

386985440

求めた総和を $10^{9} + 7$ で割ったあまりを出力することに注意してください。

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