Examining the Rooms

• problem
• solution
• code

problem

hdu 3625

solution

之前考試有一道題：最多砸開 $k$ 扇門，采取最有操作，求把 $n$ 個門都打開的方案數(shù)。

本題稍稍多了一個不能砸開第一扇門的限制，以及求的是概率。

概率好說，可行方案數(shù)除以總方案數(shù)即可，總方案數(shù)顯然是 $n$ 把鑰匙隨便放的全排列，$n!$。

先不考慮不能砸開第一扇門，即暴力開啟最多 $k$ 扇門就能開啟所有門。

注意到一扇門打開后只放著一把鑰匙，如果不是暴力開啟的門的鑰匙，那么一定會開啟另一扇門。

這可以對應到圖上的一條邊，而最后暴力開啟門的鑰匙就將這個形狀連成一個環(huán)。

且環(huán)環(huán)之間相互獨立。【只有一把鑰匙一扇門】

這就相當于是將 $n$ 扇門劃分成最多 $k$ 個圓排列的方案數(shù)。

熟悉的同學立馬反應過來這就是第一類斯特林數(shù)的定義。

$s(n,k)=s(n?1,k?1)+s(n?1,k)?(n?1)$

$s(n?1,k?1)\to n$ 自己單獨新增一個圓排列。

$s(n?1,k)?(n?1)$ 將 $n$ 放到前面 $k$ 個原排列中的某一個中去。

相當于是斷開一條邊，$u\to v?u\to n\to v$，$n$ 放任意一個位置都對應著不同的圓排列，即不同的鑰匙方案數(shù)。

一共可以放 $n?1$ 個位置，方案數(shù)就要 $\times (n?1)$。

現(xiàn)在加上不能暴力打開第一扇門的限制。

這個限制其實就是限制不能讓第一扇門單獨成為一個大小為 $1$ 的圓排列。

如果是 $n$ 個劃分成 $k$ 個圓排列，就得是 $s(n,k)?s(n?1,k?1)$。

求前綴和最后除以階乘即是所求。

code

#include <bits/stdc++.h> using namespace std; #define maxn 25 #define int long long int T, n, k; int fac[maxn]; int dp[maxn][maxn]; signed main() {dp[0][0] = fac[0] = 1;for( int i = 1; i < maxn;i ++ )for( int j = 1; j < maxn;j ++ )dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * ( i - 1 );for( int i = 1; i < maxn;i ++ ) fac[i] = fac[i - 1] * i;scanf( "%lld", &T );while( T -- ) {scanf( "%lld %lld", &n, &k );int ans = 0;for( int i = 0; i <= k;i ++ ) ans += dp[n][i];for( int i = 0;i < k;i ++ ) ans -= dp[n - 1][i];printf( "%.4f\n", 1.0 * ans / fac[n] );}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[HDU 3625] Examining the Rooms（第一类斯特林数）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。