Hdu 4063 - A Card Game

转自：随心所欲

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=4061

题目大意：
总共有m堆牌，每堆有$a_i$张数字为$i$的牌，现在随机分配牌所在的堆，使每堆牌数保持不变，然后从第一堆取一张牌，数字为$j$，则到第j堆取一张牌，然后循环如此做，直到下一堆要取的牌堆为空，则结束游戏，求游戏结束时所有牌堆为空的概率

思路：

分析：假设取的牌顺序是一个序列，那么这种序列在末尾为$1$时是和取牌序列一一对应的，且是符合“游戏结束时牌恰好被取完”的一种情况。

简证：1、在序列中，任一数$ i $的后一个数$ j$ 是必然要放在第 i 堆里的。而值为$ i $的数有$ a[i]$个，所以在 $i $后面的数也恰好$a[i]$个，所以$a[i]$个数被放到第$ i $堆，符合题目约束条件。

2、在序列中，由于游戏是从第一堆开始的，所以第一个数虽然没有前驱，但是他是放在第 $1$ 堆的。所以如果 $1$ 不为最后一个数，那么第一堆中必然有$a[1]+1$个数了，不行。

3、序列中的最后一个数 记 i ，如果不为 $1$ ，那么值 $i$ 就只有$a[i]-1$个后继了。

4、结合2、3，易知只有最后一个数为$ 1$ ，堆容量a[i]才会都符合。才能根据此序列构造一种符合的分堆及取牌（题目原意是随机取的）情况，即一一对应。

所以至此，题目转变为$N$个数的全排列，其中最后一个数为1的概率是多少。先从$a[1]$个$1$里取一个$1$，有$a[1]$种，然后剩下的$N-1$个数全排列有$(N-1)!$种，所以总共符合有$a[1]*(N-1)!$种。而$N$个数全排列有$N!$种。所以概率为$a[1]/N$。而$N = \sum a[i]$。

代码：

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define I(x) scanf("%d",&x)
using namespace std;
int main(){
    int n,a,sum,t,b,ca=0;
    I(t);
    while(t--){
        I(n);
        sum=0;
        for(int i=0;i<n;i++){
            I(a);
            sum+=a;
            if(i==0) b=a;
        }
        printf("Case %d: %.6lf\n",++ca,1.0*b/sum);
    }
    return 0;
}