問題一覧 > 通常問題

No.1202 お菓子の食べ方

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 27
作問者 : PCTprobabilityPCTprobability / テスター : hotmanwwhotmanww
2 ProblemId : 4807 / 出題時の順位表
問題文最終更新日: 2020-08-28 22:51:14

問題文

お菓子のパックが $N$ 個あります。 それぞれのパックには $1$ から $N$ の番号がついています。 それぞれお菓子のパックには、 $M$ 個お菓子の入ったケースが入っています(以後これをお菓子ケースと言います)。それぞれのケースには $1$ から $M$ の番号がついています。 ここでお菓子パックに入っているお菓子の合計とは、そのお菓子パックに含まれているお菓子ケースに入っているお菓子の個数の和とします。 そしてお菓子パック $i$ の中のお菓子ケース $j$ に入っているお菓子の個数は $S_{i,j}$ です。 ただし、 $i \ge 2$ なら、 $S_{i,j} \le S_{i-1,j}$ 、 $j \ge 2$ なら、 $S_{i,j} \le S_{i,j-1}$ ということが保証されます。 この時 $P$ 君は以下の操作の内どれかをお菓子がなくなるまで行います。

  • 操作$1$ 全てのお菓子ケースから、入っているならお菓子を $1$ 個ずつ食べる。
  • 操作$2$ 全てのお菓子パックに対して、その中で一番入っているお菓子が多いケースのお菓子を全て食べる。ただし該当するお菓子パックに対して入っているお菓子の個数が同じものが複数存在する時は、その内ケースの番号が最も小さいものを食べる。
  • 操作$3$ 全てのお菓子パックの内、入っているお菓子の合計が最も多いお菓子パックのお菓子を全て食べる。ただし合計が同じものが複数存在する時は、その内パックの番号が最も小さいものを食べる。
この時操作の仕方としてあり得るものは何通りあるか出力してください。 ここで操作が異なるとは、操作の回数が異なる又は操作回数を $N$ として $1$ 以上 $N$ 以下の整数 $i$ が存在して $i$ 回目の操作で選んだものが異なる時またその時に限り当てはまります。 答えは非常に大きくなることがあるので $1000000007$ で割った余りを出力してください。 21:28 制約を変更しました(変数の名前が間違っていました)

入力

$N$ $M$
$S_{1,1}\ S_{1,2}\ \dots\ S_{1,M}$
$S_{2,1}\ S_{2,2}\ \dots\ S_{2,M}$
...
$S_{N,1}\ S_{N,2}\ \dots\ S_{N,M}$

  • 入力は全て整数である。
  • $1 \le N,M \le 1000=10^3$
  • $1 \le S_{i,j} \le 1000000=10^6$
  • $i \ge 2$ なら $S_{i,j} \le S_{i-1,j}$
  • $j \ge 2$ なら $S_{i,j} \le S_{i,j-1}$

出力

操作の仕方としてあり得るものの数を $1000000007$ で割った余りを出力し最後に改行してください。

サンプル

サンプル1
入力
2 3
4 3 2
3 2 1
出力
63

サンプル2
入力
5 2
100 99
98 97
96 95
94 93
92 91
出力
937854048

$1000000007$ で割った余りを出力してください。

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