No.122 傾向と対策:門松列(その3)
問題文
ここ数日で門松列に関する問題が頻出しております.
ここでは演習を通じて,門松列に対する理解を深め,門松列の問題が出題された時に解けるようになっておきましょう.
門松列対策講座を受講される皆様は既にご存知かと思いますが,門松列とは $3$ 個の要素からなる数列 $a,b,c$ で以下の $2$ つの条件を満たすものです.
・$a,b,c$ は全て異なる
・$3$ つの要素の中で $b$ が最も大きい,または,$b$ が最も小さい
この問題では通常の門松列ではなく,最近ブームになりつつあるスーパーリッチ門松列を考えましょう.
スーパーリッチ門松列とは $7$ 個の要素からなる数列 $a,b,c,d,e,f,g$ で以下の $2$ つの条件を満たすものです.
・$a,b,c,d,e,f,g$ は全て異なる
・$\min(b,d,f) > \max(a,c,e,g)$ または $\max(b,d,f) < \min(a,c,e,g)$
(直感的には,全要素異なり,偶数番目の要素が小さい方から3つ,または,大きい方から3つになっているということです.ジグジグザグザグ)
由岐さんは得体の知らないものをよく知るための第一歩は数えることだと思っています.
そこで,各要素 $x=a,b,c,d,e,f,g$ の下限 $x_{\min}$ と上限 $x_{\max}$ が与えられるので,$x_{\min} \leq x \leq x_{\max}$ を満たし,更に全ての要素が整数からなるスーパーリッチ門松列の数を数えるプログラムを書いてください.
ただし,答えは大きくなるかもしれないので答えを $10^9+7$ で割った余りを出力してください.
入力
$a_{\min}$ $a_{\max}$ $b_{\min}$ $b_{\max}$ $c_{\min}$ $c_{\max}$ $d_{\min}$ $d_{\max}$ $e_{\min}$ $e_{\max}$ $f_{\min}$ $f_{\max}$ $g_{\min}$ $g_{\max}$
$1 \leq x_{\min} \leq x_{\max} \leq 20000 = 2 \times 10^4$($x=a,b,c,d,e,f,g$)
出力
条件を満たすスーパーリッチ門松列の数 ${\rm modulo}\ 10^9+7$ の値を出力してください.
サンプル
サンプル1
入力
6 8 3 10 7 10 8 12 4 10 1 9 7 16
出力
8
条件を満たすスーパーリッチ門松列は以下の $8$ 個です:
$6, 10, 7, 11, 4, 9, 8$
$6, 10, 7, 11, 5, 9, 8$
$6, 10, 7, 12, 4, 9, 8$
$6, 10, 7, 12, 5, 9, 8$
$6, 10, 8, 11, 4, 9, 7$
$6, 10, 8, 11, 5, 9, 7$
$6, 10, 8, 12, 4, 9, 7$
$6, 10, 8, 12, 5, 9, 7$
サンプル2
入力
1 7 1 7 1 7 1 7 1 7 1 7 1 7
出力
288
$3! \times 4! \times 2$ になるらしい.
あ,そうか,この場合,置換で,$b,d,f$ が大きいか小さいかの $2$ 通りで,$b,d,f$ の並び替え方 $3!$ で,$a,c,e,g$ の並び替え方 $4!$ 通りだもんね.
サンプル3
入力
1 20000 1 20000 1 20000 1 20000 1 20000 1 20000 1 20000
出力
96826092
最大ケースです.
$10^9+7$ で割った余りを出力することを忘れないで下さい.
サンプル4
入力
2012 2019 2011 2017 2011 2018 2012 2019 2015 2015 2008 2018 2006 2019
出力
2015
新年あけましておめでとうございます.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。