LightOJ1027 A - A Dangerous Maze（n次独立重复试验之几何分布）

题意

有n扇门，对应n个数，其中有正数有负数，你现在开始挑。

挑中正数等对应时间就可以出去，负数的话就等对应绝对值时间，清除记忆然后重挑。

问出去的时间期望，写成p/q的最简分数形式。

题解

由于清除记忆，显然是n次独立重复试验。

全是负数显然出不去，输出inf。

这样，每次实验能出去的概率p=num/n，num为正数个数。

则E(ξ)=1/p，ξ为第一次出去所用的次数。

先不考虑能不能出去，等概率抽中某一个数，则单次实验等的平均时间T是。

那么，经过期望的平均后，意味着，我等E(ξ)次一定能出去。

则等的期望时间=E(ξ)*T，化简之后即为，

求一下gcd约为最简即可。

代码实现

#include <iostream>
#include <algorithm> 
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <bitset> 
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int t,sum,num;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
} 
int main()
{sci(t);rep(k,1,t){sum=0;num=0;int n;sci(n);rep(i,0,n-1){int v;sci(v);if(v>0)sum+=v,num++;else sum-=v;}int tmp=gcd(sum,num);sum/=tmp,num/=tmp;printf("Case %d: ",k);if(num==0)puts("inf");else printf("%d/%d\n",sum,num);} return 0;
}