← 返回题目列表

AtCoder · joisc2022_c

C. 拼写错误

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

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

スペルミス (Misspelling) - 原题 PDF 第 1 页
原题PDF第1页
スペルミス (Misspelling) - 原题 PDF 第 2 页
原题PDF第2页
スペルミス (Misspelling) - 原题 PDF 第 3 页
原题PDF第3页
スペルミス (Misspelling) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                         Contest 1 – Misspelling

                  スペルミス(Misspelling)



 K 理事長は,長さN の英小文字からなる文字列S を忘れてしまった.しかし,K 理事長は様々なスペル

ミスを記したスペルミス辞典を持っており,以前文字列S のスペルミスについて調べたことがあった.そ

のため,文字列S に関して以下の情報を覚えている.

    • 文字列Ti (1 ≦i ≦N) をS のi 文字目を削除して詰めた文字列と定義する.このとき,各j (1 ≦j ≦M)
    について,TAj ≦TBj である.

 ここで,TA j ≦TBj とは,TAj がTBj と同じであるか,TAj がTBj より辞書順(アルファベット順)で小さ
いことを意味する.

 K 理事長が覚えている文字列S に関する情報が与えられたとき,この情報と矛盾しない文字列S の個数

を1 000 000 007 で割った余りを出力するプログラムを作成せよ.


入力


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


    N M

      A1 B1
      A2 B2
                                 ...

     AM BM


出力

 標準出力に,情報と矛盾しない文字列S の個数を1 000 000 007 で割った余りを1 行で出力せよ.





                      スペルミス– 1 / 4

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                         Contest 1 – Misspelling



制約

    • 2 ≦N ≦500 000.

    • 1 ≦M ≦500 000.
    • 1 ≦A j ≦N (1 ≦j ≦M).
    • 1 ≦Bj ≦N (1 ≦j ≦M).
    • Aj , Bj (1 ≦j ≦M).
    • (Aj, Bj) , (Ak, Bk) (1 ≦j < k ≦M).


小課題

    1. (8 点) N ≦10.

    2. (20 点) N ≦200.
    3. (29 点) M = N −1 であり,ある(1, 2, . . . , N) を並べ替えた長さN の順列P が存在してA j = Pj かつ
      Bj = Pj+1 (1 ≦j ≦M) である.
    4. (32 点) N ≦20 000.

    5. (11 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   3 2                            5876

   1 3

   3 2

 例えばS がbab であるとき,T1 = ab,T2 = bb,T3 = ba であり,T1 ≦T3 かつT3 ≦T2 を満たすから,情
報と矛盾しない.それ以外のものも含めると,情報と矛盾しない文字列S は全部で5876 個あるため,5876

を出力する.

 一方,例えばS がaab であるときは,T1 = ab,T2 = ab,T3 = aa であり,T1 ≦T3 を満たさないから,

情報と矛盾する.

 この入力例はすべての小課題の制約を満たす.





                      スペルミス– 2 / 4

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2022 (Komaba, Tokyo)


                                                                         Contest 1 – Misspelling


  入力例2              出力例2

   5 6                            656981

   1 2

   1 5

   2 4

   5 4

   5 3

   4 3

 この入力例は小課題1, 2, 4, 5 の制約を満たす.


  入力例3              出力例3

   10 9                           206289833

   3 6

   4 6

   6 7

   7 9

   10 8

   9 8

   8 5

   5 2

   5 1

 情報と矛盾しない文字列S は824 206 295 601 個あるから,824 206 295 601 を1 000 000 007 で割った余

りである206 289 833 を出力する.

 この入力例は小課題1, 2, 4, 5 の制約を満たす.





                      スペルミス– 3 / 4

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2022 (Komaba, Tokyo)


                                                                        Contest 1 – Misspelling


 入力例4              出力例4

 7 6                            7125651

 1 3

 3 4

 4 6

 6 5

 5 7

 7 2

この入力例はすべての小課題の制約を満たす.


 入力例5              出力例5

 5 4                            61451

 2 4

 4 3

 3 5

 5 1

この入力例はすべての小課題の制約を満たす.





                     スペルミス– 4 / 4