No.122 Trends and Countermeasures: Kadomatsu Sequences (Part 3)
タグ : / 解いたユーザー数 41
作問者 :
LayCurse
Problem Statement
Problems about Kadomatsu sequences have been appearing frequently in the past few days.
Here, let us deepen our understanding of Kadomatsu sequences through practice, so that we can solve them when such problems are set.
As those of you taking this Kadomatsu sequence preparation course may already know, a Kadomatsu sequence is a sequence $a,b,c$ of $3$ elements satisfying the following $2$ conditions.
・$a,b,c$ are all distinct
・Among the $3$ elements, $b$ is the largest, or $b$ is the smallest
In this problem, instead of ordinary Kadomatsu sequences, let us consider super-rich Kadomatsu sequences, which are becoming popular lately.
A super-rich Kadomatsu sequence is a sequence $a,b,c,d,e,f,g$ of $7$ elements satisfying the following $2$ conditions.
・$a,b,c,d,e,f,g$ are all distinct
・$\min(b,d,f) > \max(a,c,e,g)$ or $\max(b,d,f) < \min(a,c,e,g)$
(Intuitively, all elements are distinct, and the even-positioned elements are the 3 smallest or the 3 largest. Zig-zig-zag-zag.)
Yuki believes that the first step to understanding something mysterious is to count it.
So, given the lower bound $x_{\min}$ and upper bound $x_{\max}$ of each element $x=a,b,c,d,e,f,g$, write a program that counts the super-rich Kadomatsu sequences that satisfy $x_{\min} \leq x \leq x_{\max}$ and whose elements are all integers.
Since the answer may be large, output the answer modulo $10^9+7$.
Input
$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$)
Output
Output the number of super-rich Kadomatsu sequences satisfying the conditions, ${\rm modulo}\ 10^9+7$.
Sample
Sample 1
Input
6 8 3 10 7 10 8 12 4 10 1 9 7 16
Output
8
The super-rich Kadomatsu sequences satisfying the conditions are the following $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$
Sample 2
Input
1 7 1 7 1 7 1 7 1 7 1 7 1 7
Output
288
Apparently this comes out to $3! \times 4! \times 2$.
Ah, I see: in this case, they are permutations, so there are $2$ ways for $b,d,f$ to be the larger or the smaller ones, $3!$ ways to arrange $b,d,f$, and $4!$ ways to arrange $a,c,e,g$.
Sample 3
Input
1 20000 1 20000 1 20000 1 20000 1 20000 1 20000 1 20000
Output
96826092
This is the maximum case.
Do not forget to output the answer modulo $10^9+7$.
Sample 4
Input
2012 2019 2011 2017 2011 2018 2012 2019 2015 2015 2008 2018 2006 2019
Output
2015
Happy New Year.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。