FOJ Problem 2257 Saya的小熊饼干

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

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 <iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
#define INF 0x3f3f3f3f
int 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
",ans);
    }
    
    return 0;
}