hdu 5245 Joyful(期望的计算，好题)

Sakura has a very magical tool to paint walls. One day, kAc asked Sakura to paint a wall that looks like an M×N matrix. The wall has M×N squares in all. In the whole problem we denotes (x,y) to be the square at the x-th row, y-th column. Once Sakura has determined two squares (x1,y1) and (x2,y2), she can use the magical tool to paint all the squares in the sub-matrix which has the given two squares as corners.However, Sakura is a very naughty girl, so she just randomly uses the tool for K times. More specifically, each time for Sakura to use that tool, she just randomly picks two squares from all the M×N squares, with equal probability. Now, kAc wants to know the expected number of squares that will be painted eventually.

The first line contains an integer T(T≤), denoting the number of test cases.For each test case, there is only one line, with three integers M,N and K.
It is guaranteed that ≤M,N≤, ≤K≤.

For each test case, output ''Case #t:'' to represent the t-th case, and then output the expected number of squares that will be painted. Round to integers.

对于一种染色方案能够覆盖方块[x,y]时
①[x1,y1]取在区域1内时，[x2,y2]可以在5、、、9四个区域内任取;
②[x1,y1]取在区域2内时，[x2,y2]可以在4、、、、、9六个区域内任取;
③[x1,y1]取在区域3内时，[x2,y2]可以在4、、、8四个区域内任取;
④[x1,y1]取在区域4内时，[x2,y2]可以在2、、、、、9六个区域内任取;
⑤[x1,y1]取在区域5内时，[x2,y2]可以在所有区域内任取;
⑥[x1,y1]取在区域6内时，[x2,y2]可以在1、、、、、8六个区域内任取;
⑦[x1,y1]取在区域7内时，[x2,y2]可以在2、、、6四个区域内任取;
⑧[x1,y1]取在区域8内时，[x2,y2]可以在1、、、、、6六个区域内任取;
⑨[x1,y1]取在区域1内时，[x2,y2]可以在1、、、5四个区域内任取;