hdu 2643
/*
?第二類Stirling數(shù)是把包含n個(gè)元素的集合劃分為正好k個(gè)非空子集的方法的數(shù)目。
?遞推公式為:
?S(n,k) = 0(n<k||k=0),
?S(n,n) = S(n,1) = 1,
?S(n,k) = S(n-1,k-1) + kS(n-1,k).
?*/
#include<stdio.h> #define LL long long #define nmax 101 #define nnum 20090126LL LL num[nmax][nmax], fac[nmax]; void init() { int i, j; for (i = 1, fac[0] = 1; i < nmax; i++) { fac[i] = fac[i - 1] * i % nnum; } for (i = 1; i < nmax; i++) { num[i][1] = 1; num[i][0] = 0; } for (i = 2; i < nmax; i++) { for (j = 1; j < nmax; j++) { if (i == j) { num[i][i] = 1; } else { num[i][j] = (num[i - 1][j - 1] + num[i - 1][j] * j) % nnum; } } } } int main() { #ifndef ONLINE_JUDGE freopen("in.data", "r", stdin); #endif init(); int T, N, i; LL res; while (scanf("%d", &T) != EOF) { while (T--) { scanf("%d", &N); for (i = 1, res = 0; i <= N; i++) { res += num[N][i] * fac[i]; res %= nnum; } printf("%I64d\n", res); } } return 0; }
?
hdu 2512
#include<stdio.h> #define nmax 2001 #define nnum 1000 int num[nmax][nmax]; void init() { int i, j; for (i = 1; i < nmax; i++) { num[i][0] = 0, num[i][1] = 1; } for (i = 2; i < nmax; i++) { for (j = 1; j < nmax; j++) { if (i == j) { num[i][i] = 1; continue; } num[i][j] = (num[i - 1][j - 1] + num[i - 1][j] * j) % nnum; } } } int main() { #ifndef ONLINE_JUDGE freopen("in.data", "r", stdin); #endif int n, x, i, res; init(); while (scanf("%d", &n) != EOF) { while (n--) { scanf("%d", &x); for (i = 1, res = 0; i <= x; i++) { res += num[x][i]; res %= nnum; } printf("%d\n", res); } } return 0; }
Bell數(shù),又稱為貝爾數(shù)。
是以埃里克·坦普爾·貝爾(Eric Temple Bell)為名的。
B(n)是包含n個(gè)元素的集合的劃分方法的數(shù)目。
B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5,
B(4) = 15, B(5) = 52, B(6) = 203,...
遞推公式為,
B(0) = 1,
B(n+1) = Sum(0,n) C(n,k)B(k). n = 1,2,...
其中,Sum(0,n)表示對(duì)k從0到n求和,C(n,k) = n!/[k!(n-k)!]
-------------------------
Stirling數(shù),又稱為斯特靈數(shù)。
在組合數(shù)學(xué),Stirling數(shù)可指兩類數(shù),都是由18世紀(jì)數(shù)學(xué)家James Stirling提出的。
第一類Stirling數(shù)是有正負(fù)的,其絕對(duì)值是包含n個(gè)元素的集合分作k個(gè)環(huán)排列的方法數(shù)目。
遞推公式為,
S(n,0) = 0, S(1,1) = 1.
S(n+1,k) = S(n,k-1) + nS(n,k)。
第二類Stirling數(shù)是把包含n個(gè)元素的集合劃分為正好k個(gè)非空子集的方法的數(shù)目。
遞推公式為,
S(n,n) = S(n,1) = 1,
S(n,k) = S(n-1,k-1) + kS(n-1,k).
將n個(gè)有區(qū)別的球的球放入k個(gè)無標(biāo)號(hào)的盒子中( n>=k>=1,且盒子不允許為空)的方案數(shù)就是stirling數(shù).(即含 n 個(gè)元素的集合劃分為 k 個(gè)集合的情況數(shù))
遞推公式:
S(n,k) = 0 (k > n)
S(n,1) = 1 (k = 1)
s(n,k)=1 (n=k)
S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)
分析:設(shè)有n個(gè)不同的球,分別用b1,b2,...,bn表示。從中取出一個(gè)球bn,bn的放法有以下兩種:
1.bn獨(dú)占一個(gè)盒子,那么剩下的球只能放在k-1個(gè)盒子里,方案數(shù)為S(n-1,k-1);
2.bn與別的球共占一個(gè)盒子,那么可以將b1,b2,...,bn-1這n-1個(gè)球放入k個(gè)盒子里,然后將bn放入其中一個(gè)盒子中,方案數(shù)為k*S(n-1,m).
-------------
bell數(shù)和stirling數(shù)的關(guān)系為,
每個(gè)貝爾數(shù)都是"第二類Stirling數(shù)"的和。
B(n) = Sum(1,n) S(n,k).
hdu 2643 Rank hdu 2512 一卡通大冒險(xiǎn) stirling (斯特靈數(shù))的應(yīng)用
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號(hào)聯(lián)系: 360901061
您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
