問題一覧 > 通常問題

No.1202 How to Eat Sweets

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : PCTprobability / テスター : hotman78
お気に入りにしたユーザー ProblemId : 4807 / 自分の提出
問題文最終更新日: 2020-08-28 22:51:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 263 (順位表) の他の問題:

Problem Statement

There are $N$ packs of sweets. The packs are numbered from $1$ to $N$. Each pack of sweets contains $M$ cases that hold sweets (hereafter called sweet cases). The cases in each pack are numbered from $1$ to $M$. Here, the total number of sweets in a pack is defined as the sum of the numbers of sweets in the sweet cases contained in that pack. The number of sweets in sweet case $j$ of pack $i$ is $S_{i,j}$. It is guaranteed that $S_{i,j} \le S_{i-1,j}$ if $i \ge 2$, and $S_{i,j} \le S_{i,j-1}$ if $j \ge 2$. $P$-kun repeatedly performs one of the following operations until no sweets remain.

  • Operation $1$: From every sweet case, eat $1$ sweet if the case contains any.
  • Operation $2$: For every pack of sweets, eat all the sweets in the case containing the most sweets in that pack. If multiple cases in the pack contain the same largest number of sweets, eat from the one with the smallest case number among them.
  • Operation $3$: Among all packs of sweets, eat all the sweets in the pack with the largest total number of sweets. If multiple packs have the same largest total, eat from the one with the smallest pack number among them.
Output the number of possible ways to perform the operations. Two ways of operating are different if and only if the numbers of operations differ, or, letting $N$ be the number of operations, there exists an integer $i$ between $1$ and $N$, inclusive, such that the operations chosen for the $i$-th operation differ. Since the answer can be very large, output it modulo $1000000007$. 21:28 The constraints were changed (a variable name was wrong).

Input

$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}$

  • All inputs are integers.
  • $1 \le N,M \le 1000=10^3$
  • $1 \le S_{i,j} \le 1000000=10^6$
  • $S_{i,j} \le S_{i-1,j}$ if $i \ge 2$
  • $S_{i,j} \le S_{i,j-1}$ if $j \ge 2$

Output

Output the number of possible ways to perform the operations modulo $1000000007$, followed by a newline.

Sample

Sample 1
Input
2 3
4 3 2
3 2 1
Output
63

Sample 2
Input
5 2
100 99
98 97
96 95
94 93
92 91
Output
937854048

Output the answer modulo $1000000007$.

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