TCO'10 Online Round 3 1000pt

题目大意：

密码串由小写字母、大写字母和数字组成，要求求出小写字母个数不少于L个、大写字母个数不少于U个、数字个数不少于D个的长度为N密码串的种数。

答案对 1000000009 取模

解题思路：

自己不会，看了neal_wu的代码，表示膜拜。

令a表示小写字母个数，b表示大写字母个数，c表示数字个数，则a>=L,b>=U,c>=D,a+b+c=N。

按照一般来讲会首先想到枚举数字个数再枚举小写字母个数，然后就用组合数求种数，这个是最自然的想法，但是时间复杂度不堪忍受。

这题有个规律，

因为数字比较特殊，它只有10种，而小写字母和大写字母都是26种，所以小写字母和大写字母可以一起考虑，然后用组合数区分种数，于是先枚举数字。

当数字个数为c时，种数num=sum{pow(10,c)*choose(N,c)*pow(26,N-c)*choose(N-c,k)},L<=k<=N-c-U

考虑到c是枚举量，所以num=pow(10,c)*pow(26,N-c)*choose(N,c)*sum{choose(N-c,k)},L<=k<=N-c-U

于是num的值跟一段连续的组合数求和有关，只要能o(1)求出sum{choose(N-c,k)},L<=k<=N-c-U的值，就能O(1)求出num的值，就能O(n)解决问题。

设H(c)=sum{choose(N-c,k)},L<=k<=N-c-U

可以得之有递推式：H(c-1)=2*H(c)+choose(N-c,L-1)+choose(N-c,N-c-U+1);

初始条件: 　　　 H(N-L-D)=choose(N-c,L);

所以c从N-L-D往下枚举到D，维护H(c)的递推值，就能O(n)解决该题。

思考中：

因为这题涉及到杨辉三角中的一个正的三角形，它要求的值ans等于那个三角形的一行的和乘以一个无关紧要系数的值的和，所以可以用一个值维护行的和就能避免O(n^2)枚举值，降低一维复杂度。

在正三角形中假设H(i)表示第i行的值的和以及第i行是杨辉三角的第Y(i)行，起点是这一行的第X(i)个，

则H(1)=choose(Y(i),X(i))

H(i+1)=2*H(i)+choose(Y(i),X(i)-1)+choose(Y(i),X(i)+i)

在倒三角形中也是可以递推H(i)的,H(1)表示最下面的那一个值，

H(1)=choose(Y(i),X(i))

H(i+1)=(H(i)-choose(Y(i)-1,X(i)-1)-choose(Y(i)-1,X(i)+i-1))/2+choose(Y(i)-1,X(i)-1)+choose(Y(i)-1,X(i)+i-1)

也可以O(1)维护。

巴特西