NKOJ 1725 数字（数位dp）

P1725数字

问题描述

给出一个整数n和一个数组a。数组a中包含十个整数，编号0到9。
你的任务是统计满足下列条件的正整数的个数：
1.该正整数的长度不能超过n位；
2.该正整数的最高位不能是0；
3.数字i(0<=i<=9)在该正整数中至少出现a[i]次。

输入格式

第一行一个整数n(1<=n<=100)。
第二行，10个空格间隔的整数，表示a[0],a[1]…a[9]里面存的数字

输出格式

一行，一个整数，表示满足条件的数字的个数，结果可能很大，输出与1000000007取模后的结果。

样例输入1：

1
0 0 0 0 0 0 0 0 0 1

样例输入2：

2
1 1 0 0 0 0 0 0 0 0

样例输入3：

3
1 1 0 0 0 0 0 0 0 0

样例输入1：

1

样例输入2：

1

样例输入3：

36

---

用$F[i][j]$表示用数字$[j,9]$构成长度为$i$的数字的方案数。

递推方程：$F[i][j]=\sum F[i-k][j+1]*C_{i}^{k}$

意味着在$i$个位置中放$k$个数字$j$，这样就保证了满足题目条件，然后剩下的位置上放$[j+1,9]$的排列方式就是$F[i-k][j+1]$

关于$0$需要特殊讨论，因为$0$不能放首位，因此有$F[i][0]=\sum F[i-k][1]*C_{i-1}^{k}$

---

代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 105
#define ll long long
using namespace std;
ll n,C[N][N],mod=1000000007,a[N],F[N][10],ans;
int main()
{
	ll i,j,k;
	scanf("%lld",&n);
	for(i=0;i<=9;i++)scanf("%lld",&a[i]);
	
	for(i=0;i<=n;i++)C[i][0]=1;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;//预处理组合数
	
	for(i=a[9];i<=n;i++)F[i][9]=1;//赋初值
	
	for(j=8;j>=1;j--)
	for(i=a[j];i<=n;i++)
	for(k=a[j];k<=i;k++)F[i][j]=(F[i][j]+F[i-k][j+1]*C[i][k])%mod;
	
	for(i=a[0];i<=n;i++)
	for(k=a[0];k<=i;k++)
	if(i>0)F[i][0]=(F[i][0]+F[i-k][1]*C[i-1][k])%mod;
	
	for(i=1;i<=n;i++)ans=(ans+F[i][0])%mod;
	cout<<ans;
}