一个密码是由大小写字母与数字组成的序列。计算长度为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;

}