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


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