No.1684 Find Brackets
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : Sumitacchan / テスター : 👑 hitonanode 👑 ygussany
タグ : / 解いたユーザー数 33
作問者 : Sumitacchan / テスター : 👑 hitonanode 👑 ygussany
問題文最終更新日: 2021-12-31 19:22:38
問題文
(
と)
のみからなる長さ $N$ の文字列 $S$ に対して次の問題を考え、その答えを $f(S)$ とします。
文字列 $T$ は次の $2$ つの条件をともに満たしている(このような $T$ は常に存在することが証明できます)。例えば $S={}$
文字列 $T$ の長さとしてありうる最小値はいくつか。
- $T$ は
(
と)
のみからなり、正しい括弧列である(正しい括弧列の定義は下の補足を参照してください)。- $S$ は $T$ の部分文字列である。すなわち、$T$ の連続する部分列に $S$ と一致するものが存在する。
)(
のときは、条件を満たす $T$ で長さが最小のものは $T={}$()()
であるため、$f(S)=4$ になります。また、$S={}$
()
のときは、$T={}$()
とできるため、$f(S)=2$ になります。
文字列 $S$ として、(
を $M$ 個以上含むようなものを考えることにします(そのような $S$ は $\sum_{i=M}^N\binom{N}{i}$ 通りあります)。
そのような全ての $S$ に関して $f(S)$ の総和を取った値を求めてください。
答えは非常に大きくなることがあるので $10^9+7$ で割った余りを出力してください。
補足:正しい括弧列とは次のように定義されます。
- 空文字列は正しい括弧列である。
- 文字列 $A$ が正しい括弧列であるとき、
(
$,A,$)
をこの順に並べた文字列も正しい括弧列である。 - 文字列 $A,B$ が正しい括弧列であるとき、$A,B$ をこの順に並べた文字列も正しい括弧列である。
- 上記1~3のいずれかの条件を満たす文字列のみが正しい括弧列である。
入力
$N\ \ M$
- $1\le N\le 10^6$
- $0\le M\le N$
- 入力は全て整数である。
出力
$f(S)$ の総和を $10^9+7$ で割った余りを出力してください。
サンプル
サンプル1
入力
2 2
出力
4
$S={}$((
のみを考えれば良いです。$T={}$(())
とできるため、$f(S)=4$ です。
サンプル2
入力
2 1
出力
10
サンプル1の例に加えて、$S={}$()
$,$ )(
の場合を考えます。
サンプル3
入力
998244 353
出力
293243454
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。