← 返回题目列表

AtCoder · joisc2009_abduction

abduction. 绑架

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

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

誘拐 (Abduction) - 原题 PDF 第 1 页
原题PDF第1页
誘拐 (Abduction) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Abduction: 誘拐


input ファイル“abduction.in”
output 標準出力
ソースファイルabduction.c/abduction.cpp
時間制限1 秒/ データ


 ある晴天の日のこと.X はY を誘拐した.X はY に目隠しをして,車に乗せ,誘拐現場から

X の自宅までY を連れて市街地を移動した.

 幸い,警察たちの尽力により,X は囚われの身となり,この事件はめでたく解決した.しか

し,X の犯行の動機だけは謎のままとなった.

 探偵であるあなたは,犯人X の犯行動機に強い関心を持っていて,さまざまな調査を行って

いた.そんな中,あなたは,X の「誘拐現場から自宅までの移動経路」が何通り考えられるか,

ということを調べる必要に迫られた.

 犯人X がY を連れて走った市街地は,南北にW + 1 本,東西にH + 1 本の道路が走る碁盤

目状の街であり,誘拐現場は南西隅の曲がり角に,X の自宅は北東隅の曲がり角に位置してい

る.また,Y の証言によって,X が左折,右折をどのような順番で何回行ったかが分かってい

る.さらに,犯人X は,移動中に同じ交差点や道を二度以上通っている可能性もあるし,自宅

の前に来ても止まらずに通過したかもしれない.ただし犯人X は,U ターンは一度も行ってい

ないものとする.

 たとえば,(W, H) = (4, 3) とするとき,市街地は下図のようになるが,犯人X が太線の経路

で移動した場合,Y の証言は「左折,右折,右折,右折,左折,左折,左折」となる.

                                           X の自宅





         誘拐現場

 犯人X の移動経路として考えられる場合の数を10 000 000(= 107) で割った余りを求めるプ

ログラムを書け.

                            誘拐–1/2

Input. 入力ファイルabduction.in の1 行目には2 つの整数W, H (1 ≦W, H ≦1000) が書

かれている.これは,南北,東西に走る道路の本数がそれぞれW + 1 本,H + 1 本であること

を表す.

  2 行目には,1 つの整数N(1 ≦N ≦10 000) が書かれている.これは,Y の証言の長さを表す.

  3 行目には,各文字がL またはR である,長さN の文字列が与えられる.i 文字目がL であ

る場合,i 回目にX が左折したことを表し,またR である場合は,i 回目にX が右折したことを

表す.

Output. 出力は,標準出力に行うこと.移動経路の場合の数を10 000 000(= 107) で割った

余りを表す1 つの整数を出力せよ.

採点基準採点用データのうち,配点の40% 分については,W, H ≦40 を満たす.


例1
 abduction.in 標準出力
 4 3           80
 7
 LRRRLLL

例2
 abduction.in 標準出力
 4 4           9
 3
 RLR





                            誘拐–2/2