問題一覧 > 通常問題

No.1684 Find Brackets

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : SumitacchanSumitacchan / テスター : 👑 hitonanodehitonanode 👑 ygussanyygussany
5 ProblemId : 6809 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-29 18:34:49

問題文

()のみからなる長さ $N$ の文字列 $S$ に対して次の問題を考え、その答えを $f(S)$ とします。

文字列 $T$ は次の $2$ つの条件をともに満たしている(このような $T$ は常に存在することが証明できます)。
  • $T$ は()のみからなり、正しい括弧列である(正しい括弧列の定義は下の補足を参照してください)。
  • $S$ は $T$ の部分文字列である。すなわち、$T$ の連続する部分列に $S$ と一致するものが存在する。
文字列 $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$ で割った余りを出力してください。


補足:正しい括弧列とは次のように定義されます。

  1. 空文字列は正しい括弧列である。
  2. 文字列 $A$ が正しい括弧列であるとき、($,A,$ ) をこの順に並べた文字列も正しい括弧列である。
  3. 文字列 $A,B$ が正しい括弧列であるとき、$A,B$ をこの順に並べた文字列も正しい括弧列である。
  4. 上記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もしくは右上の雲マークをクリックしてアカウントを作成してください。