以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 3 – Deciphering
解読(Deciphering)
あなたはA からZ の文字で書かれたIOI 国の機密文書を手に入れた.この機密文書の原文はIOI 語で書
かれている.機密文書からいくつかの文字(0 文字でもよい)を消すことで原文が得られる.
IOI 語の文章は1 文字以上からなる文字列であり,相異なるM 個の次のような規則を満たす:
規則i (1 ≦i ≦M):文字Ai の直後に文字Bi は来ない.
与えられた機密文書の原文として考えられるものの個数を10 000 000 で割った余りを求めよ.ただし,消
し方が異なっても同じ原文であれば1 つと数える.
課題
機密文書から考えられる原文の個数を10 000 000 で割った余りを求めよ.
制限
1 ≦L ≦300 000 機密文書の長さ
0 ≦M ≦26 × 26 IOI 語の規則の個数
入力
標準入力から以下の入力を読み込め.
• 1 行目には整数L が書かれており,機密文書の長さがL であることを表す.
• 2 行目には機密文書が書かれている.これは長さL のA からZ までの文字からなる文字列である.
• 3 行目には整数M が書かれており,IOI 語の規則の個数がM であることを表す.
• 続くM 行にはIOI 語の規則の情報が書かれている.i + 3 行目(1 ≦i ≦M) には,規則i を表すA から
Z までの文字Ai, Bi が空白を区切りとして書かれている.Ai = Aj かつBi = Bj なる規則j ( j , i) は存
在しない.
出力
標準出力に考えられる原文の個数を10 000 000 で割った余りを1 行で出力せよ.
解読– 1 / 2
Japanese Olympiad in Informatics 2010/2011
Qualifying Trial
April 23–24, May 3–5, 2011, Tokyo/Osaka
Contest Day 3 – Deciphering
採点基準
採点用データのうち,配点の10%分については,L ≦15 を満たす.
採点用データのうち,配点の40%分については,L ≦5 000 を満たす.
入出力の例
入力例1 出力例1
5 15
JOIOI
1
I O
この入力例では,I, II, J, JI, JII, JO, JOI, JOII, JOO, JOOI, O, OI, OII, OO, OOI が考えられる原文である.
入力例2 出力例2
26 7108863
ABCDEFGHIJKLMNOPQRSTUVWXYZ
0
解読– 2 / 2