No.801 エレベーター

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 134
作問者 : tempura_pptempura_pp / テスター : heno_codeheno_code
24 ProblemId : 2813 / 出題時の順位表

問題文

てんぷらくんは$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$で割った余りを答えてください。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。