傳送門
Joyful
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 781 Accepted Submission(s): 339
Problem Description
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.
Input
The first line contains an integer T(T≤100), 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 1≤M,N≤500, 1≤K≤20.
Output
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.
Sample Input
2
3 3 1
4 4 2
Sample Output
Case #1: 4
Case #2: 8
Hint
The precise answer in the first test case is about 3.56790123.
Source
The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest
題目大意：
就是有一個 m*n 的矩陣方格，然後你每次取兩個方格，分別是(x1,y1)和(x2,y2);然後就是每次覆蓋一個子矩陣是以(x1,y1)和(x2,y2)為對角線構成的矩陣，讓你求的就是你進行 k 次之後得到的方格數的期望。
解題思路：
其實這個題，畫一下就行了而且非常清楚，我也不會畫，我就用語言描述啦，我們先求一下總的方案數，第一個方格是m*n,第二個方格還是m*n,那麼總的方案數就是 m^2*n^2,假設我們選的(i, j)點就是沒有被覆蓋的點，那麼我們選的那兩個方格肯定是 i行上面的和下面的 j列左面的和右面的，但是我們重復了那4個角（其實也不能叫角，應該叫子矩陣），所以我們要減去那四個角的矩陣，假設結果是ans，那麼概率顯然就是 p = ans/(m^2*n^2)然後我們取了k次之後就是p^k,那麼被覆蓋的概率就是 1-p^k,然後我們進行的就是 兩個循環 for(i: 1-m)，for(j: i-n)，那麼每次都對1-p^k進行累加得到的就是期望，注意的就是m^2*n^2會爆int,
最後的結果是四捨五入的，有一個小竅門（四捨五入的時候加上0.5就行了）
My Code：
#include
#include
using namespace std;
typedef long long LL;
int main()
{
int T;
cin>>T;
for(int cas=1; cas<=T; cas++)
{
LL m, n, k;
cin>>m>>n>>k;
LL tot = (m*n) * (m*n);
double ret = 0;
for(LL i=1; i<=m; i++)
{
for(LL j=1; j<=n; j++)
{
LL up = ((i-1)*n) * ((i-1)*n);
LL down = ((m-i)*n) * ((m-i)*n);
LL left = ((j-1)*m) * ((j-1)*m);
LL right = ((n-j)*m) * ((n-j)*m);
LL leftup = ((i-1)*(j-1)) * ((i-1)*(j-1));
LL rightup = ((n-j)*(i-1)) * ((n-j)*(i-1));
LL leftdown = ((j-1)*(m-i)) * ((j-1)*(m-i));
LL rightdown = ((m-i)*(n-j)) * ((m-i)*(n-j));
LL ans = up + down + left + right- leftup - rightup - leftdown - rightdown;
///cout< 
