← 返回题目列表

AtCoder · joisc2018_c

C. 帐篷

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

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

テント  (Tents) - 原题 PDF 第 1 页
原题PDF第1页
テント  (Tents) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 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