caozy623's Blog

题意：
给定数n和10个数的数组a，求满足以下条件的数的个数
1、数的长度不超过n
2、这个数不含前导0
3、数字i至少出现a[i]次

典型的数位DP，我们设f[i][j]为前i位数使用了j-9的数字能得到的数的个数
首先枚举长度len，对j的不同情况进行讨论：
1、j=9，此时若len>=a[9]，那么f[len][9]=1否则为0
2、0<j<9，此时考虑枚举数字j时，j+1到9已经枚举完毕。此时j的个数可以为k(a[j]<=k<=len)，
对于每个k放置在数列中的方法显然有C(len,k)种。那么状态转移方程即为f[len][j]+=f[len-k][j+1]*c[len][k]
其中c是组合数。
3、j=0，此时因为不能有前导0，所以对于0来说放置的方法只有len-1种，个数上限也是len-1，别的细节和第二种情况的是差不多的。
中间注意步步取模，注意是长度不超过n，所以最后输出sum（f[i][0]）{0<=i<=n}即可

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
#define hzy 1000000007
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
    return x*f;
}

inline void read(char *s,int &ts)
{
char x=getchar();
while(!(x>='a'&&x<='z'))x=getchar();
while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
ll f[110][10];
ll c[110][110];
int n;
int a[20];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<=9;i++)
    scanf("%d",&a[i]);
    for(int i=0;i<=n;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j-1]+c[i-1][j])%hzy;
    }
    //for(int i=1;i<=n;i++)
    //for(int j=1;j<=i;j++)
    //printf("%d\n",c[i][j]);
    for(int len=0;len<=n;len++)
    {
        if(len>=a[9]) f[len][9]=1;
        else f[len][9]=0;
        for(int j=8;j>=1;j--)
        for(int k=a[j];k<=len;k++)
        f[len][j]=(f[len][j]+f[len-k][j+1]*c[len][k])%hzy;
        for(int k=a[0];k<=len-1;k++)
        f[len][0]=(f[len][0]+f[len-k][1]*c[len-1][k])%hzy;
    }
    ll ans=0;
    for(int i=0;i<=n;i++)
    ans=(ans+f[i][0])%hzy;
    printf("%I64d\n",ans);
    return 0;
}