Problem 2257 Saya的小熊饼干

Accept: 23    Submit: 80

Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

Saya最近喜欢上了小熊饼干，但是他有非常严重的选择困难症，当然面对这一堆小熊饼干的时候，想起了一句至理名言“犹豫不决么？ 那就来RAND()一下吧！”。

于是，Saya把小熊饼干排成了一个N*M的矩阵，每个位置上都放着一块小熊饼干。每当他想吃小熊饼干的时候，他就运行一下代码。（random()为生成一个任意正整数）。

x1=random() mod N+1;

y1=random() mod M+1;

x2=random() mod N+1;

y2=random() mod M+1;

然后将以(x1, y1)，(x2, y2)为两个顶点的，四条边平行于边界的一个子矩形内的小熊饼干全部吃掉（两个点的连线为矩形的对角线，如果x1=x2或者y1=y2，则认为矩形的长度或宽度为1）。显然，如果某个位置上的小熊饼干已经被吃掉了，那Saya就什么都吃不到了。

在这题中，我们假定random()函数非常完美，得到每个格子的概率相等。

请你帮忙算一算，K次之内她期望可以吃到块小熊饼干？

 Input

 

包含多组测试数据。

一行内包括三个正整数K，N，M。

0≤K≤10000，1≤N，M≤1000

 Output

一个整数，K次之内期望可以吃到的小熊饼干块数（四舍五入精确到整数）。

Sample Input

1 3 3

Sample Output

4

 Hint

对于样例简单的解释是这样的：在3*3的格子里取子矩形，取到1*1的方案数为9，取到1*2或2*1的方案数为24，取到1*3或3*1的方案数为12，取到2*2的方案数为16，取到2*3或3*2的方案数为16，取到3*3的方案数为4结果约为（1*9+2*24+3*12+4*16+6*16+9*4） / (9*9) = 3.5679，四舍五入后得4。

PS：最后Saya直接令x1=1，y1=1，x2=n，y2=m。 

 

思路：一块一块饼干考虑过去，设事件Xij：坐标在(x,y)处的饼干被吃掉。则每块饼干被吃掉这些事件之间相互独立，则设事件X:n,m矩形内所有的饼干被吃掉，E(X)=ΣE(Xij),1<=i<=n,1<=j<=m,那么只要求出每一个E(Xij)，最后累加即可。

对于E(Xij)=1*P(Xij),而P(Xij)=(2x(n-x+1)-1)/(n^2)*(2y(n-y+1)-1)/m^2;

AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define INF 0x3f3f3f3fint k,n,m;double mod_pow(double x,int k) { double res = 1; while (k) { if (k & 1)res = res*x; x = x*x; k >>= 1; } return res;}int main() { while (scanf("%d%d%d",&k,&n,&m)!=EOF) { double ans = 0; for (int x= 1; x <= n;x++) { for (int y = 1; y <= m;y++) { double Pxy = (2.0*x*(n - x + 1) - 1)/(n*n)*(2.0*y*(m-y+1)-1) /(m*m);//!计算式中至少一个double型 ans += 1 - mod_pow(1- Pxy, k); } } printf("%.0f\n",ans); } return 0;}
            
           
          
         
        
       
      

---