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




可复制的 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