← 返回题目列表

AtCoder · joisc2020_f

F. 最古老的废墟 3 (废墟 3)

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

最古の遺跡 3 (Ruins 3) - 原题 PDF 第 1 页
原题PDF第1页
最古の遺跡 3 (Ruins 3) - 原题 PDF 第 2 页
原题PDF第2页
最古の遺跡 3 (Ruins 3) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                         Contest Day 2 – Ruins 3

            最古の遺跡3 (Ruins 3)



 ジョイ教授はIOI 国の歴史の研究の第一人者である.IOI 国に関する神殿の調査中に,ジョイ教授は何本

かの石柱が建てられた跡と古代のIOI 国の住民が書いたとされる古文書を発見した.古文書には石柱につい

て詳しく書かれていた.具体的には以下の内容が書かれていた.

    • 建設された直後には2N 本の石柱が存在し,それぞれに1 から2N までの番号が付けられていた.

    • 建設された直後には,高さがk (1 ≦k ≦N) の石柱はちょうど2 本存在した.

    • N 回の地震が発生し,各回の地震ごとに何本かの石柱が崩れて石柱の高さが1 低くなった.ただし,

   一部の石柱は住民が支えていたため崩れずに高さは変わらなかった.

    • 地震発生時には,それぞれのk (1 ≦k ≦N) について,ちょうど1 本の高さk の石柱が住民によって

   支えられた.もし地震発生時に高さk の石柱が複数本存在する場合は,番号が最も大きい石柱が支え
   られた.すなわち,地震直前の石柱i (1 ≦i ≦2N) の高さをhi としたとき,石柱i が支えられる条件
    は,hi ≧1,かつ,すべてのj > i に対しh j , hi が成り立つことである.
    • N 回の地震後に残った,すなわち高さが1 以上である石柱はN 本であった.

 建設された直後の2N 本の石柱の高さを復元できれば世紀の大発見であると考えたジョイ教授は,石柱が
建てられた跡を詳しく調査した.調査の結果,N 回の地震後に残った石柱の番号はA1, A2, . . . , AN であるこ

とがわかった.

 この情報と古文書に書かれていたことに合致するような,建設された直後の2N 本の石柱の高さとして考

えられるのは何通り存在するのか気になったジョイ教授は,弟子であるあなたに場合の数を計算するプログ

ラムを作るよう依頼した.

 N 回の地震後に残った石柱の番号が与えられたとき,建設された直後の2N 本の石柱の高さとして考えら

れる場合の数を1 000 000 007 で割ったときの余りを求めるプログラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.


    N

      A1 · · · AN





                      最古の遺跡3– 1 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                         Contest Day 2 – Ruins 3



出力

 標準出力に,建設された直後の2N 本の石柱の高さとして考えられる場合の数を1 000 000 007 で割った

ときの余りを1 行で出力せよ.


制約

    • 1 ≦N ≦600.
    • 1 ≦Ai ≦2N (1 ≦i ≦N).
    • Ai < Ai+1 (1 ≦i ≦N −1).


小課題

    1. (6 点) N ≦13.

    2. (52 点) N ≦60.

    3. (42 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   3                              5

   3 4 6

 例えば,石柱の高さが石柱1 から順に(2, 2, 3, 3, 1, 1) であったとする.高さがk (1 ≦k ≦3) であるような

石柱はちょうど2 本存在するので古文書の情報と合致している.

    • 1 回目の地震の際,石柱2, 4, 6 が住民によって支えられたので,地震直後の石柱の高さは(1, 2, 2, 3, 0, 1)

   となる.

    • 2 回目の地震の際,石柱3, 4, 6 が住民によって支えられたので,地震直後の石柱の高さは(0, 1, 2, 3, 0, 1)

   となる.

    • 3 回目の地震の際,石柱3, 4, 6 が住民によって支えられたので,地震直後の石柱の高さは(0, 0, 2, 3, 0, 1)

   となる.

 よって,3 回の地震後に残った石柱は石柱3, 4, 6 である.これは入力で与えられた情報と合致する.

 その他の石柱の高さとして考えられるのは(2, 3, 2, 3, 1, 1), (2, 3, 3, 2, 1, 1), (3, 2, 2, 3, 1, 1), (3, 2, 3, 2, 1, 1)  



                      最古の遺跡3– 2 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2020 (Komaba, Tokyo)


                                                                         Contest Day 2 – Ruins 3


の4 通りのみである.

 したがって,地震後に残った石柱の番号と古文書の情報に合致するような6 本の石柱の高さは5 通りで

ある.



  入力例2              出力例2

   1                              0

   1

 古文書に合致するような石柱の高さは(1, 1) のみであり,1 回の地震後の高さは(0, 1) になる.

 したがって,地震後に残った石柱の番号と古文書の情報に合致するような2 本の石柱の高さは0 通りで

ある.



  入力例3              出力例3

   10                             147003663

   5 8 9 13 15 16 17 18 19 20

 建設された直後の2N 本の石柱の高さとして考えられるものは111 147 004 440 通りあるから,

111 147 004 440 を1 000 000 007 で割った余りである147 003 663 を出力する.





                      最古の遺跡3– 3 / 3