問題一覧 > 通常問題

No.801 エレベーター

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 219
作問者 : tempura_pp / テスター : heno239
36 ProblemId : 2813 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-03-17 20:10:47

問題文

てんぷらくんはN階建てのビルの1階にいます。このビルにはM台のエレベーターがあり、 それぞれ1からMまでの番号が1つずつつけられています。 エレベーターiはLi階からRi階までの各階に止まります。 てんぷらくんはこれらのエレベーターを使ってちょうどk回移動をしました。 ここで、1回の「移動」とは具体的には以下の手順のことをいいます。

  • 今いる階をx階として、Li≤x≤Ri をみたすようなエレベーターiを1つ選び、 エレベーターiに乗ってLi≤y≤Ri をみたすy階で降りる。 なお、x=yであってもよく、この場合もエレベーターiに乗ったとみなす。
k回の移動の後てんぷらくんがN階にいるような移動方法が何通りあるかを109+7で割った余りを求めてください。 ただし、2つの移動方法が異なるとは以下の2つの条件のうち少なくとも1つが成り立つことをいいます。
  • あるjが存在してj回目の移動で乗ったエレベーターが異なる。
  • あるjが存在してj回目の移動後にいる階が異なる。

ごめんなさい

writerの貧弱な知識でPython3で書くとTLEしました。同じコードをPyPy3で提出したらAC(約900ms)でした。

入力

N M K
L1 R1
L2 R2
⋮
LM RM

  • 1≤N, M, K≤3000
  • 1≤Li≤Ri≤N
  • 入力はすべて整数

出力

移動方法の個数を109+7で割った余りを1行に出力してください。

サンプル

サンプル1
入力
2 2 2
1 2
1 2
出力
8

エレベーターiに乗ってj階に移動することを(i,j)と書くと、以下の8通りが条件をみたします。

  • (1, 1), (1, 2)
  • (1, 1), (2, 2)
  • (2, 1), (1, 2)
  • (2, 1), (2, 2)
  • (1, 2), (1, 2)
  • (1, 2), (2, 2)
  • (2, 2), (1, 2)
  • (2, 2), (2, 2)
乗るだけ乗って移動しなくてもいいことや同じ性能のエレベーターが複数台ありえることに注意してください。

サンプル2
入力
5 1 5
2 2
出力
0

1階から乗ることのできるエレベーターも5階で降りることのできるエレベーターも存在しません。
2階から動くことのできないエレベーターに意味はあるのでしょうか。

サンプル3
入力
8 6 10
2 7
1 8
2 8
1 8
2 8
4 6
出力
70138606

109+7で割った余りを答えてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。