← 返回题目列表

AtCoder · joisc2011_deciphering

deciphering. 破译

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

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

解読 (Deciphering) - 原题 PDF 第 1 页
原题PDF第1页
解読 (Deciphering) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 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