A - Area Sum
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 行 M 列からなる盤面があり,各マス目には row-major 順に 1 から N \times M までの整数が書かれています. つまり,上から i 行目,左から j 列目のマスに書かれている整数を A_{i,j} で表すことにすると, A_{i,j}=(i-1) \times M + j です.
この盤面の部分長方形であって,その内部に書かれた値の総和がちょうど V になるものの個数を数えてください.
より厳密に言えば,整数の 4 つ組 (a,b,c,d) (1 \leq a \leq b \leq N, 1 \leq c \leq d \leq M) であって,\sum_{a \leq i \leq b,\ c \leq j \leq d} A_{i,j}=V を満たすものの個数を数えてください.
制約
- 1 \leq N, M \leq 5000
- 1 \leq V \leq 10^{15}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N M V
出力
答えを出力せよ.
入力例 1
2 2 3
出力例 1
2
盤面には以下のように整数が書き込まれています.
12 34
条件を満たす部分長方形は,(a,b,c,d)=(1,1,1,2),(2,2,1,1) の 2 つです.
入力例 2
2 2 5
出力例 2
0
入力例 3
13 8 1032
出力例 3
5