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 <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 = ;
while (k) {
if (k & )res = res*x;
x = x*x;
k >>= ;
}
return res;
} int main() {
while (scanf("%d%d%d",&k,&n,&m)!=EOF) {
double ans = ;
for (int x= ; x <= n;x++) {
for (int y = ; y <= m;y++) {
double Pxy = (2.0*x*(n - x + ) - )/(n*n)*(2.0*y*(m-y+)-) /(m*m);//!计算式中至少一个double型
ans += - mod_pow(- Pxy, k);
}
}
printf("%.0f\n",ans);
} return ;
}

05-11 22:55