いろいろ解き方があるらしい。
最小全域木（Minimum Spanning Tree）問題なのだが、どの頂点とどの頂点を結んでもよいので、辺が$N(N-1)/2$本と見なせる。 MSTの基礎的な解法であるクラスカル法では、$O(E \log{V})$ で、とても間に合わない。
コストが定式で表されているので、その特徴を利用して、無駄な辺を除外する。
解説の解法の図化は、このサイトが詳しい。
で、規模の小さい都市から更新しつつ区間の最小値を求めるにはセグメント木を使えば良いのだが、Pythonではそれでも遅い。
証明がよくわかっていない。
サンプル4などを、実際にどの都市とどの都市が結ばれるのかやってみると、特徴的な結果になる。
,-------------------,-----------, 43 94 27 3 69 99 56 25 8 15 46 8 | | `--'|'--' | | `--' `--' `--' | `------'|`------' | `----------' `----------'
3,8,8をハブとして、周辺都市が全てそこと結ばれた上で、隣接するハブ同士が結ばれる構造となっている。
これが、都市の数が大きくなっても成り立つのでは？
ハブ都市の検出は、（自分より規模が小さいという条件無しで）各都市から見た左右それぞれのコスト最小都市を計算し、「左からも右からも対象とされている」都市のみを抜き出すと、なんか知らんが上手くいった。
数学問題? 理屈さえわかれば数式で表現できるので、それを求めるだけ。階乗を求める必要があるので計算量は$O(K)$ではあるが、本当に$K$回、数をかけるだけで、他は$O(1)$で実装できる。
解説の解法は、読めば簡単に理解出来るくらい単純ですごい！綺麗！となるんだけど、思いつかんわ……。
$H,W$ が大きいので、1マス毎に数えるのは、動的計画法などを使っても無理。
横に切った回数 $h$ と縦に切った回数 $w$ で、$h+w$ 回目のコストは$(h+1)(w+1)$として求められる。そこに、そのように切る瞬間を含む切り方の数をかける。これを、全ての$h,w$について求める、というのがまず思いつく方法だが、これも計算量が$O(HW)$となり無理。
以下では、さらに$k=h+w$として$k$が同じ$h,w$をまとめて式変形を重ねることで、計算量を$O(K)$としている。
解説では「紙片の数と一対一に対応するもの」として、「マス(i,j)が紙片の左下になっているものの数」としている。
そうすると、「$i$ 番目の横線と $j$ 番目の縦線がともに切られた瞬間から、以降その紙片については毎回1コストずつかかる」と言い換えることができる。
これは多くのマスで期待値が等しくなるので、たった3通りのパターンさえ考えればよくなる。
($t$ 回目にはじめて$(i,j)$が紙片の左下になる切り方の数)×(以降の操作回数 $K-t+1$) を、$t=1..K$ まで合計すればよい。$\sum{k}$ や $\sum{k^2}$ の公式を利用すると簡単になる。
def solve(h, w, k):
n = h + w
MOD = 10 ** 9 + 7
if k == 1:
return 2 * n
ans = 0
# (0, 0) ... k * nPk * 1
ans += k * n * (n - 1) % MOD
# (i, 0) (0, j) ... sum(t for t=1..k) * (n-1)P(k-1) * (h+w)
tmp = k * (k + 1) // 2 * (n - 1) % MOD
ans += tmp * n % MOD
# (i, j) ... sum((t-1)(k-t+1) for t=1..k) * (n-2)P(k-2) * 2 * h*w
# ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = (k-1)k(k+1)/6
tmp = (k - 1) * k * (k + 1) // 3 % MOD
ans += tmp * h * w % MOD
for m in range(n - 2, n - k, -1):
ans = ans * m % MOD
return ans % MOD
h, w, k = map(int, input().split())
print(solve(h, w, k))