Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

排列组合

Posted by willsmith at 2011-05-21 12:39:44 on Problem 3786
假设有n=20,k=8   先看k,如果k是8,则说明string中的1至少有9个,因为只有连续的9个1才可能生成一个8,而如果存在不连续的1的话,那么1的个数必定大于9个,那么此时问题就如下:
如果只有9个1 那么所有1必定是连在一起的,即1 1 1 1 1 1 1 1 1 ,而此时的问题就转化为在1的间隙中插入11个0,求出其种数,由于1连续,所以只能在两旁插入,就只有C(12,1)*C(8,0)(组合数),
如果有10个1的话,那么在这10个1之间必定有一个空隙,即可能是1 1 1 1 1 0 1 1 1 1 1
也可能是 1 1 1 1 1 0 0 1 1 1 1 1,此时问题又转化为在10个1之间的九个空隙中,找出一个空隙,然后将其余的10个0放入到这3个空隙中(别忘了左右两个空隙总是存在的,即0可以随便放在string的最左边或最右边),那么问题又转化为C(11,2)*C(9,1)
接下去可以递推,11个1,12个1......的情况
其公式就为:
C(12,1)*C(8,0)+C(11,2)*C(9,1)+C(10,3)*C(10,2)+C(9,4)*C(11,3)+C(8,5)*C(12,4)+C(7,6)*C(13,5)
其中C(12,1)和C(11,2)..........:这个主要是用了插板法,当有11个0要插入到两个空隙时,可以转化为有11个相同的球,用一块板将其划分为两个部分,那么此时由于11个球,有12个空隙可以插入(包括左右空隙),所以是C(12,1),同样,C(11,2)即可转化为有10个球,中间有11个空隙,要用两块板将其划分为三个部分,那么就是C(11,2)

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator