#defineLLlonglong#definenmax101#definennum20090126LLLLnum[nmax][nmax],fac[nmax];voidinit(){i" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

hdu 2643 Rank hdu 2512 一卡通大冒險(xiǎn) stirling

系統(tǒng) 1713 0

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;

}


    
小知識(shí):

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).

參考資料: http://planetmath.org/?op=getobj&from=objects&id=9059

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ì)您有幫助就好】

您的支持是博主寫作最大的動(dòng)力,如果您喜歡我的文章,感覺我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 成人嫩草研究院永久网址 | 日韩va| 91激情视频| 久久97久久97精品免视看清纯 | 亚洲天天做夜夜做天天欢人人 | 国产精品一区二区不卡 | 亚洲韩国日本一级二级r级 亚洲韩精品欧美一区二区三区 | 一级毛片免费播放 | 桃花阁成人网在线观看 | 国产伦精品一区二区三区 | 国产一区二区三区久久精品 | 国产一区亚洲 | 亚洲 欧美 bt | 亚洲免费精品 | 日日摸夜夜添夜夜添人人爽 | 免费观看成人碰视频公开 | 一本色道久久88加勒比—综合 | 6一10周岁毛片在线 717影院理论午夜伦八戒 | 成人国产三级精品 | 99热在线国产 | 黄页在线播放网址 | 欧美成人禁片在线观看网址 | 国产精品久久久影院 | 手机看片福利日韩欧美看片 | 国产精品福利视频 | 老司机毛片 | 中国国产一国产一级毛片视频 | vvideos欧美极度另类 | 国产一级淫片a视频免费观看 | 四虎永久在线精品视频播放 | 色网站在线播放 | 久操免费视频 | 久久国产精品高清一区二区三区 | 午夜国产福利视频 | 美利坚永久精品视频在线观看 | 国产专区在线播放 | 四虎国产永久在线观看 | 欧美精品在线一区二区三区 | 国产拍在线 | 毛片免费全部播放一级 | 国产精品日韩欧美一区二区三区 |