自己做网站需要的技术,个人简历表格下载,套模板建设网站多少钱,md主题 wordpressExamining the Roomsproblemsolutioncodeproblem
hdu 3625
solution
之前考试有一道题#xff1a;最多砸开 kkk 扇门#xff0c;采取最有操作#xff0c;求把 nnn 个门都打开的方案数。
本题稍稍多了一个不能砸开第一扇门的限制#xff0c;以及求的是概率。
概率好说最多砸开 kkk 扇门采取最有操作求把 nnn 个门都打开的方案数。
本题稍稍多了一个不能砸开第一扇门的限制以及求的是概率。
概率好说可行方案数除以总方案数即可总方案数显然是 nnn 把钥匙随便放的全排列n!n!n!。
先不考虑不能砸开第一扇门即暴力开启最多 kkk 扇门就能开启所有门。
注意到一扇门打开后只放着一把钥匙如果不是暴力开启的门的钥匙那么一定会开启另一扇门。
这可以对应到图上的一条边而最后暴力开启门的钥匙就将这个形状连成一个环。
且环环之间相互独立。【只有一把钥匙一扇门】
这就相当于是将 nnn 扇门划分成最多 kkk 个圆排列的方案数。
熟悉的同学立马反应过来这就是第一类斯特林数的定义。
s(n,k)s(n−1,k−1)s(n−1,k)∗(n−1)s(n,k)s(n-1,k-1)s(n-1,k)*(n-1)s(n,k)s(n−1,k−1)s(n−1,k)∗(n−1)
s(n−1,k−1)→ns(n-1,k-1)\rightarrow ns(n−1,k−1)→n 自己单独新增一个圆排列。
s(n−1,k)∗(n−1)s(n-1,k)*(n-1)s(n−1,k)∗(n−1) 将 nnn 放到前面 kkk 个原排列中的某一个中去。
相当于是断开一条边u→v⇒u→n→vu\rightarrow v\Rightarrow u\rightarrow n\rightarrow vu→v⇒u→n→vnnn 放任意一个位置都对应着不同的圆排列即不同的钥匙方案数。
一共可以放 n−1n-1n−1 个位置方案数就要 ×(n−1)\times (n-1)×(n−1)。
现在加上不能暴力打开第一扇门的限制。
这个限制其实就是限制不能让第一扇门单独成为一个大小为 111 的圆排列。
如果是 nnn 个划分成 kkk 个圆排列就得是 s(n,k)−s(n−1,k−1)s(n,k)-s(n-1,k-1)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;
}
