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


可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Tents
テント(Tents)
JOI 君はキャンプ場を経営している.このキャンプ場は縦H 行,横W 列の区画に区切られている.キャ
ンプ場の縦方向は南北方向に平行であり,横方向は東西方向に平行である.北からi 行目,西からj 列目
(1 ≦i ≦H, 1 ≦j ≦W) にある区画を区画(i, j) と書く.
このキャンプ場に何張かのテントを設営することになった.1 張のテントはちょうど1 つの区画を占め
る.2 張以上のテントが同じ区画を占めることはない.
それぞれのテントは,東西南北の4 つの方向のうち,ちょうど1 つの方向に出入口を持つ必要がある.
また,テントの出入口の方向は以下の条件を満たす必要がある.
• 区画(i1, j) および区画(i2, j) (1 ≦i1 < i2 ≦H, 1 ≦j ≦W) にともにテントを設営する場合,区画(i1, j)
のテントの出入口は南を,区画(i2, j) のテントの出入口は北を向いていなければならない.
• 区画(i, j1) および区画(i, j2) (1 ≦i ≦H, 1 ≦j1 < j2 ≦W) にともにテントを設営する場合,区画(i, j1)
のテントの出入口は東を,区画(i, j2) のテントの出入口は西を向いていなければならない.
JOI 君はキャンプ場に上記の条件を満たすように1 張以上のテントを設営する方法の数を知りたくなっ
た.なお,テントを設営する方法2 つは,ある区画が存在し,2 つの設営方法におけるその区画でのテン
トの置かれ方(テントの有無や,出入口の方向) が異なる場合,区別する.
課題
キャンプ場の情報が与えられたとき,キャンプ場に問題文の条件を満たすように1 張以上のテントを設
営する方法の数を1 000 000 007 で割った余りを求めるプログラムを作成せよ.
入力
標準入力から以下の入力を読み込め.
• 1 行目には2 個の整数H, W が空白を区切りとして書かれている.これらはJOI 君が経営するキャン
プ場が縦H 行,横W 列の区画に区切られていることを表す.
出力
キャンプ場に問題文の条件を満たすように1 張以上のテントを設営する方法の数を1 000 000 007 で割っ
た余りを一行で出力せよ.
テント– 1 / 2
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
Spring Training Camp/Qualifying Trial
March 19–25, 2018 (Komaba/Yoyogi, Tokyo)
Contest Day 1 – Tents
制限
すべての入力データは以下の条件を満たす.
• 1 ≦H ≦3 000.
• 1 ≦W ≦3 000.
小課題
この課題では小課題が全部で2 個ある.各小課題の配点および追加の制限は以下の通りである.
小課題1 [48 点]
以下の条件を満たす.
• 1 ≦H ≦300.
• 1 ≦W ≦300.
小課題2 [52 点]
追加の制限はない.
入出力例
入力例1 出力例1
1 2 9
東方向,西方向,南方向,北方向に出入口を持つテントをそれぞれ文字’E’,’W’,’S’,’N’ で表すこ
とにするとき,条件を満たすテントの設営方法は以下に示す9 通りある.
E W S N
E W S N
E W
入力例2 出力例2
4 3 3252
入力例3 出力例3
100 100 561068619
テント– 2 / 2