問題一覧 > 通常問題

No.122 Trends and Countermeasures: Kadomatsu Sequences (Part 3)

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 41
作問者 : LayCurse
お気に入りにしたユーザー ProblemId : 298 / 自分の提出
問題文最終更新日: 2026-06-25 03:49:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 74 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。