题目大意：

每次随机选择两个点，便把这两个点之间形成的子矩阵上的每一个方块涂色，问随机选择k次，整个m*n的矩阵中有多少个小方块被涂上了颜色

 

这道题不难，但自己智商实在捉急，一直想不出来。。。

因为这里n,m<=500,所以总共250000个方块，我们可以考虑的是每一个方块在随机选择1次后被染色的概率 p[i][j]

那么k次后就变成了 1-(1-p[i][j])^k的概率了，我们将所有概率相加就得到了总共的染色块数

至于怎么计算被染色概率就是可以将整个矩形块分解，然后去计算所有不能包括当前点的所有点对组合，求出不被染色的次数

总的次数n*m*n*m 会超int

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 using namespace std; 7 #define N 505 8 #define ll long long 9 double p[N][N];10 int n , m , k;11 //计算i,j位置的正方形小块不包含的取点总数12 ll cal(int i , int j)13 {14     ll c1 = i-1 , c2=(i-1)*(m-j) , c3=m-j , c4=(n-i)*(m-j);15     ll c5 = n-i , c6=(n-i)*(j-1) , c7=j-1 , c8=(i-1)*(j-1);16     ll ret = 0;17     ret+=c1*(c1+c2+c8)+c2*(c2+c1+c8+c3+c4)+c3*(c2+c3+c4)+c4*(c2+c3+c4+c5+c6)+c5*(c4+c5+c6)+c6*(c4+c5+c6+c7+c8)+c7*(c6+c7+c8)+c8*(c6+c7+c8+c1+c2);18   //  if(ret<0 || ret>n*m*n*m) cout<
          <<" "<
           
            <<" "<
            
             <
             
              >=1;29 }30 return ret;31 }32 33 int main()34 {35 #ifndef ONLINE_JUDGE36 freopen("a.in" , "r" , stdin);37 #endif38 int T , cas=0;39 scanf("%d" , &T);40 while(T--)41 {42 scanf("%d%d%d" , &n , &m , &k);43 double ret = 0;44 ll all = (ll)n*m*n*m;45 // cout<
              
               <
               
                =1||p[i][j]<0) cout<
                <<" "<
                 
                  <<" "<
                  
                   <