問題一覧 > 通常問題

No.801 エレベーター

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

問題文

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

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

ごめんなさい

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

入力

$N\ M\ K$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_M\ R_M$

  • $1\le N,\ M,\ K\le 3000$
  • $1\le L_i \le R_i \le N$
  • 入力はすべて整数

出力

移動方法の個数を$10^9+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

$10^9+7$で割った余りを答えてください。

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