一个密码是由大小写字母与数字组成的序列。计算长度为N且含有至少L个小写字母，U个大写字母，D个数字的密码个数。(1<=N<=200000,0<=L,U,D<=n)。答案模1,000,000,009
【输入格式】
第1行：1个整数N第2行：1个整数L第3行：1个整数U第4行：1个整数D【输出格式】第1行：1个整数，表示答案。
本弱在考试时遇到这个题的时候，果断N^2骗分，正解神马的完全不知道。听了大神讲了之后，发现这个题的解法真是太精妙了。
首先，我们应该先把数字单独分离出来计算，把小写和大写字母放在一起比较容易处理。如果数字有x个，那么方案数就有f[N-x]*26^(N-X)*10^x*C(N,x)，f[n]为字母（不区分大小写,不区分字母是否相同）为n个的方案数。
暴力计算f[n]的复杂度是n^2的，但本弱经过模拟样例，发现了一个规律：f[n]=2*f[n-1]+C(n-1,cnt)+C(i-1,L-1);
其中cnt的初值是L，每次cnt的值要+1
其实把f[n]展开成C的形式，再用杨辉三角就很好理解了。
本弱的代码如下：
#include<iostream>#include<cstdio>using namespace std;typedef long long LLint;const LLint MOD=1000000009LL;const LLint MAXN=210000;LLint U,D,N,L;LLint Jie[MAXN],Jie_Ni[MAXN],P10[MAXN],P26[MAXN];void Ex_Gcd(LLint a,LLint b,LLint &d,LLint &x,LLint &y){ if(!b){ d=a; x=1; y=0; } else{ Ex_Gcd(b,a%b,d,y,x); y-=x*(a/b); }}void Init(){ Jie[0]=1; Jie_Ni[0]=1; P10[0]=1; P26[0]=1; for(LLint i=1;i<=N;i++){ Jie[i]=Jie[i-1]*i%MOD; LLint x,y,d; Ex_Gcd(Jie[i],MOD,d,x,y); Jie_Ni[i]=(x+MOD)%MOD; P10[i]=P10[i-1]*10LL%MOD; P26[i]=P26[i-1]*26LL%MOD; }}LLint Get_C(LLint Down,LLint Up){ if(Up>Down) return 0LL; return (MOD+Jie[Down]*Jie_Ni[Up]%MOD*Jie_Ni[Down-Up]%MOD)%MOD;}LLint f[MAXN],Ans,cnt;int main(){ scanf("%I64d%I64d%I64d%I64d",&N,&L,&U,&D); Init(); for(LLint i=L;i<=L+U-U;i++) f[L+U]=(f[L+U]+Get_C(L+U,i)+MOD)%MOD; cnt=L; for(LLint i=L+U+1;i<=N-D;i++){ cnt++; f[i]=(2*f[i-1]%MOD+Get_C(i-1,cnt)+Get_C(i-1,L-1)+MOD)%MOD; } for(LLint i=D;i<=N-L-U;i++) Ans=(Ans+f[N-i]*P26[N-i]%MOD*P10[i]%MOD*Get_C(N,i)%MOD+MOD)%MOD; printf("%I64d",Ans);return 0;}
转载于:https://www.cnblogs.com/Return-0/archive/2013/03/18/2966735.html
相关资源：Victor 版本1.3.3.5