题目描述

难度分:$1900$

输入$n(1 \leq n \leq 100)$和长为$10$的数组$a(0 \leq a[i] \leq 100)$。

有多少个长度为至多为$n$的正整数，无前导零，且数字$0$~$9$分别至少出现 $a[0],a[1],…,a[9]$次？答案模$10^9+7$。

输入样例$1$

1
0 0 0 0 0 0 0 0 0 1

输出样例$1$

1

输入样例$2$

2
1 1 0 0 0 0 0 0 0 0

输出样例$2$

1

输入样例$3$

3
1 1 0 0 0 0 0 0 0 0

输出样例$3$

36

算法

记忆化搜索

比较容易想到的是从$1$到$n$枚举长度$i$，然后看每个长度有多少种方案，全部加起来就是答案。

状态定义

$dp[i][j]$表示用$\geq j$的数组构造长度为$i$的数字有多少种方案，我们的答案就是$\Sigma_{i=1}^{n}dp[i][0]$。

状态转移

$base$ $case$：

如果$j=9$，那此时就要用$9$这个数字构造一个长度为$i$的数字，需要$i \geq a[9]$才能出一个合法的方案。

一般情况：

1. 如果$j \gt 0$，那么就枚举$j$这个数字的个数$k$，在$i$个位置中选$k$个位置上放置$j$这个数字。$[j+1,9]$的数字之后再考虑，根据乘法原理，状态转移方程为$dp[i][j]=\Sigma_{k=a[j]}^{i}dp[i-k][j+1] \times C(i,k)$。
2. 如果$j=0$，还是要枚举$0$的个数，但是$0$不能放在最高位，所以只有$i-1$个位置给它放，状态转移方程为$dp[i][j]=\Sigma_{k=a[j]}^{i}dp[i-k][j+1] \times C(i-1,k)$。

复杂度分析

时间复杂度

需要进行$O(n)$次动态规划，状态数量是$O(10n)$，单次转移需要枚举数字$j$的个数，时间复杂度是值域级别，值域是$O(n)$的。因此，整个算法的时间复杂度为$O(10n^3)$。

空间复杂度

组合数用逆元来计算的话需要$O(n)$级别的辅助数组，DP矩阵的空间消耗就是状态的数量，为$O(10n)$。因此，算法的额外空间复杂度为$O(10n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 110, MOD = 1e9 + 7;
int T, n, a[10], dp[N][10];
LL inv[N], finv[N], f[N];

// 预处理逆元
void get_inv(int n) {
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    finv[0] = finv[1] = f[0] = f[1] = 1;
    for(int i = 2; i <= n; i++) {
        f[i] = f[i - 1] * i % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 排列数
LL A(LL n, LL m) {
    if(n == 0 || m == 0) return 1;
    return f[n] * finv[n - m] % MOD;
}

// 组合数
LL C(LL n, LL m) {
    if(m == 0) return 1;
    if(m < 0 || m > n) return 0;
    return A(n, m) * finv[m] % MOD;
}

int dfs(int i, int j) {
    if(j >= 9) return i >= a[9]? 1: 0;
    int &v = dp[i][j];
    if(v != -1) return v;
    int res = 0;
    // 枚举选k个i
    for(int k = a[j]; k <= i; k++) {
        res = (res + (LL)dfs(i - k, j + 1) * C(i - (j == 0? 1: 0), k) % MOD) % MOD;
    }
    return v = res;
}

void solve() {
    if(n == 1) {
        puts("1");
        return;
    }
    int ans = 0;
    // 枚举长度
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            for(int k = 0; k <= 9; k++) {
                dp[j][k] = -1;
            }
        }
        // 用[0,9]构造长度为i的数字方案数
        ans = (ans + dfs(i, 0)) % MOD;
    }
    printf("%d\n", ans);
}

int main() {
    get_inv(100);
    scanf("%d", &n);
    for(int i = 0; i <= 9; i++) {
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}