hdu3625

题意:

酒店发生一起谋杀案。作为镇上最好的侦探,您应该立即检查酒店的所有N个房间。但是,房间的所有门都是锁着的,钥匙刚锁在房间里,真是个陷阱!您知道每个房间里只有一把钥匙,并且所有可能的分配可能性均等。例如,如果N = 3,则有6种可能的分布,每种分布的概率为1/6。为方便起见,我们将房间编号从1到N,房间1的键编号为键1,房间2的键编号为2,依此类推。
要检查所有房间,您必须用力摧毁一些门。但是您不想破坏太多,因此您采取以下策略:首先,您手中没有钥匙,因此您会随机破坏一扇锁着的门,进入房间,检查并取出其中的钥匙。然后,也许您可​​以使用新钥匙打开另一个房间,检查一下并获得第二把钥匙。重复此操作,直到您无法打开任何新房间。如果仍然有未检查的房间,则必须随机挑选另一扇未打开的门用力摧毁,然后重复上述步骤,直到检查完所有房间为止。
现在只允许您强行摧毁最多K门。更重要的是,房间1中有一个非常重要的人物。不允许您破坏房间1的门,也就是说,检查房间1的唯一方法是使用相应的钥匙打开房间。您想知道最终检查所有房间的概率是什么。(来自一键翻译)

分析

等价于将 $n$ 个元素分成 $k$ 个子集,其中1号元素不能单独成一个子集,$k$ 可以取1至K.

所以,设 $s(n,i)$ 为第一类Stirling数,可行方案为 $\sum_{i=1}^k s(n, i)-s(n-1, i-1)$,总方案数为 $n!$

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 20 + 5;
ll fact[maxn], stir[maxn][maxn];

void init()
{
    fact[0] = 1;
    for(int i = 1;i < maxn;i++)  fact[i] = fact[i-1] * i;

    stir[0][0] = 1;
    stir[1][1] = 1;
    for(int i = 2;i < maxn;i++)
        for(int j = 1;j <= i;j++)
            stir[i][j] = stir[i-1][j-1] + (i-1)*stir[i-1][j];
}

int main()
{
    init();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, k;
        scanf("%d%d", &n, &k);
        ll ans = 0;
        for(int i = 1;i <= k; i++)
            ans += stir[n][i] - stir[n-1][i-1];
        printf("%.4f\n", 1.0*ans/fact[n]);
    }
    return 0;
}
View Code

Codejam4214486 A Password Attacker

题目链接

题意:一串长度为 $N$ 的密码恰有 $M$ 种字符组成,求可能的字符串的种数。

分析:把 $n$ 个位置看作 $n$ 个有区别的小球,问题等价于将 $n$ 个有区别的球放到 $m$ 个不同的盒子里,且无空盒的方案数,易知,方案数为 $m!s(n, m)$,其中 $s(n, m)$ 为第二类Stirling数。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 100+5;
const ll mod =1000000007;
ll fact[maxn], stir[maxn][maxn];

void init()
{
    fact[0] = 1;
    for(int i = 1;i < maxn;i++)  fact[i] = fact[i-1] * i % mod;

    stir[0][0] = 1;
    stir[1][1] = 1;
    for(int i = 2;i < maxn;i++)
        for(int j = 1;j <= i;j++)
            stir[i][j] = (stir[i-1][j-1] + j*stir[i-1][j]) % mod;
}

int main()
{
    freopen("A-large-practice.in", "r", stdin);
    freopen("a.out", "w", stdout);

    init();
    int T, kase = 0;
    scanf("%d", &T);
    while(T--)
    {
        int n, m;
        scanf("%d%d", &m, &n);
        ll ans = fact[m] * stir[n][m] % mod;
        printf("Case #%d: %lld\n", ++kase, ans);
    }
    return 0;
}
View Code

参考链接:

1. https://blog.csdn.net/doyouseeman/article/details/50876786

2. https://blog.csdn.net/ACdreamers/article/details/8521134

01-22 13:08