uestc1888 Birthday Party 　　　组合数学，乘法原理

July 18, 2013
Math

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25539#problem/G 题目意思：　　有n个人，每个人有一个礼物，每个人能拿自己礼物，n个人随机送礼物，给一个数字k,求出可以找到k个人，满足：这ｋ个人里面，第一个人把礼物给第二个人，第二个人把礼物给第三个人，以此类推，第ｋ个人把礼物给第１个人．求满足这个条件的概率．组合数学：满足条件的一组ｋ个人称为一个ｋ环，注意：可能有多个ｋ环！先考虑至少形成一个ｋ环的情况：A(n,k) * (n-1)^(n-k) / (k * (n-1)^(n)) == A(n, k) / (k * (n-1)^k) ；然后在考虑至少形成m个环的情况．设至少形成m个环的概率是：f(m) = A(n, km)/(k^mm!(n-1)^(km)) 所以只需要递推m = 1 …. m = n/k 然后可以发现：f(m)/f(m-1) = A(n, km) / (A(n, k(m-1))*k*m(n-1)^k)，因此可以根据计算出的f(1)求出f(2), f(3)．．．．根据容斥：ans = f(1) - f(2) + f(3) - f(4) + …. ORZ lyl的代码：


#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <list>
using namespace std;
#define INF 0x3f3f3f3f
const double eps=1e-9;

int main ( int argc, char *argv[] )
{
    double ans, t;
    int i, k, n, tot, j;
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r",stdin);
#endif
    while (~scanf("%d", &tot)) {
        while (tot--) {
            scanf("%d%d", &n, &k);
            for (i=0,ans=1; i<k; ans=ans*(n-i++)/(n-1));
            for (t=ans/=k,i=2; i*k<=n; ++i) {
                for (t=t/i/k,j=n-(i-1)*k; j>n-i*k; t=t*j--/(n-1));
                if (t<eps) break; else ans = i&1?ans+t:ans-t;
            }
            printf("%.9lf\n", ans);
        }
    }
        return EXIT_SUCCESS;
}

不经过深思熟虑是写不出这么精简的代码的．．．ORZ

Read more