HDU 3625 Examining the Rooms【第一类斯特灵数】

<题目链接>

<转载于 >>> >

题目大意：
有n个锁着的房间和对应n扇门的n把钥匙，每个房间内有一把钥匙。你可以破坏一扇门，取出其中的钥匙，然后用取出钥匙打开另一扇门（如果取出的钥匙能打开房门则接着打开，取出其中钥匙，如此往复，若打不开则继续破坏一扇门）。最多可以破坏k（k<=n）扇门，但是编号为1的门只能用钥匙打开。求能打开所有门（被破坏或是被钥匙打开）的概率。

解题分析：

钥匙和门的关系是成环状的，打开一个门之后，该环内的所有房间都可以进入，怎么说呢，就拿Hint里的#6来举例，Room1 Room2 Room3是在一个环当中的，假设我破坏了Room3，那么我取出Room3内的钥匙Key2就可以打开Room2，而Room2里有钥匙Key1，那我们又可以打开Room1。

因此，该题就转化成了求N个房间形成1~K个环有多少种可能，然后除以总的分配方案数即为题目要我们求的概率。

首先，总的分配方案数是比较好求的，N的全排列N！种，因为N<=20，有可能超int型范围，所以__int64或long long是必不可少的

其次就是求N个房间成i个环的种类数了，而第一类斯特林数S(N,K)=S(N-1,K-1)+(N-1)*S(N-1,k)恰恰就是求N个元素形成K个非空循环排列的方法数

剩下的就是枚举形成的环，但是要排除掉编号为1的房间独立成环的可能

S(N,M)-S(N-1,M-1)，表示N个元素形成M个环，减去1独自成环，即剩下的N-1个元素形成M-1个环，算得的结果便是所求值

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define eps 1e-7

#define LL long long

using namespace std;

LL fac[] = {  };

LL stir1[][];

void INIT()

{

    for (int i = ; i<; i++)

        fac[i] = fac[i - ] * i;    //计算阶乘

    for (int i = ; i <= ; i++)   //计算stir数组,表示让n个物品形成m个环的方案数

    {

        stir1[i][] = ;

        stir1[i][i] = ;

        for (int j = ; j<i; j++)

            stir1[i][j] = stir1[i - ][j - ] + (i - )*stir1[i - ][j];

    }

}

int main()

{

    INIT();

    int t, n, k;

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &n, &k);

        if (n ==  || k == )

        {

            printf("0.0000\n");

            continue;

        }

        LL sum = ;

        for (int i = ; i <= k; i++)

            sum += stir1[n][i] - stir1[n - ][i - ];       //减去第一个门独立成环的情况

        printf("%.4f\n", (double)sum / fac[n]);

    }

    return ;

}

2018-08-12