题目描述

难度分:$2100$

输入$n$、$k(1 \leq k \leq n \leq 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

定义幸运数字为：只包含$4$和$7$的数字。

输出$a$中有多少个长为$k$的子序列$b$，满足$b$中没有相同的幸运数字。（非幸运数字可以有一样的）答案模$10^9+7$。

注：子序列不一定连续。如果两个子序列完全一样，但有元素下标不一样，也视作不同的子序列。

输入样例$1$

3 2
10 10 10

输出样例$1$

3

输入样例$2$

4 2
4 4 7 7

输出样例$2$

4

算法

组合数学+动态规划

比较容易想到组合数学的解法框架，先遍历数组$a$，将幸运数字的频数统计在一个$counter$表中，然后将频数转移到一个数组$freqs$中。只要频数就行，这个频数对应的幸运数字究竟是哪个根本无关紧要。

这时候我们也可以很容易得到非幸运数字的个数$unlucky$，枚举长度为$k$的子序列中一共有$i \in [0,unlucky]$个非幸运数字，那么幸运数字就有$lucky=k-unlucky$个。所以非幸运数字有$i$个的情况下，能对答案的贡献就是“$C_{unlucky}^i \times$幸运数字中选出$lucky$个的方案数”，组合数是可以直接通过预处理出逆元表从而快速计算的，关键就在于如何计算后面这一部分。

动态规划

其实本质就是从$freqs$数组中选择$lucky$个数，所有可能乘积之和。因为每个幸运数被选出来的方案数都和它的频数相关，而各个幸运数是否被选出来是相互独立的，因此总的方案数就是这$lucky$个频数之积。

状态定义

$dp[i][j]$表示从前$i$个幸运数字中选择$j$个出来的方案数。对于$j=0$的情况，无论$i$取多少都满足$dp[i][0]=1$，因为空集也是一种方案。

状态转移

有两种策略进行转移：

1. 如果不选第$i$（$i \geq 1$）个数，那么前$i-1$个数中就选出来了$j$个，状态转移方程为$dp[i][j]=dp[i-1][j]$。
2. 如果选第$i$个数，它一共有$freqs[i-1]$个，可以把这个数插在前$i-1$个数选出来的$j-1$个数的集合（一共有$dp[i-1][j-1]$种方案）中，所以状态转移方程为$dp[i][j]=dp[i-1][j-1] \times freqs[i-1]$。

以上两种策略加起来就是$dp[i][j]$，从。但是我们发现$dp$是个二维的状态，它有没有可能会超时间和空间呢？其实是不可能的，因为$a[i] \leq 10^9$的值域限制，枚举长度$1$到$9$可以发现最多也就$1000$来个幸运数字，因此这个DP用平方的算法来做是没问题的，从所有幸运数字中选出$lucky$个的方案数即为$dp[tot][lucky]$，其中$tot$是幸运数字的种数。

复杂度分析

时间复杂度

预处理逆元表时间复杂度是$O(n)$的。预处理出$counter$和$freqs$需要对$a$数组中的所有数进行检查，看是不是幸运数，检查某个数$x$是否是幸运数需要对其$log_{10}x$个数位进行检查，所以时间复杂度为$O(nlog_{10}U)$，其中$U$是$a$的最大值域。

接下来的DP状态数量是$O((log_{10}U)^2)$，单次转移是$O(1)$，所以时间复杂度为$O((log_{10}U)^2)$。

最后枚举非幸运数字的个数$i \in [0,k]$统计答案，每个$i$只需要$O(1)$就能得到对答案的贡献，因此时间复杂度为$O(k)$。综上，整个算法的时间复杂度为$O(nlog_{10}U+(log_{10}U)^2+k)$。

空间复杂度

各个逆元表的空间是线性的，为$O(n)$。DP数组的空间是$O((log_{10}U)^2)$。因此，整个算法的额外空间复杂度为$O(n+(log_{10}U)^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 100010, M = 2010, MOD = 1e9 + 7;
LL inv[N], finv[N], fac[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] = fac[0] = fac[1] = 1;
    for(int i = 2; i <= n; i++) {
        fac[i] = fac[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 fac[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;
}

bool check(int x) {
    while(x) {
        int d = x % 10;
        if(d != 4 && d != 7) return false;
        x /= 10;
    }
    return true;
}

int n, k, a[N];
LL dp[M][M];

int main() {
    scanf("%d%d", &n, &k);
    get_inv(n);
    int unlucky = 0;     // 非幸运数字个数
    unordered_map<int, int> counter;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(check(a[i])) {
            // 幸运数字
            counter[a[i]]++;
        }else {
            unlucky++;
        }
    }
    int tot = counter.size();    // 幸运数字的种数
    vector<int> freqs;
    for(auto&[num, freq]: counter) {
        freqs.push_back(freq);
    }
    for(int i = 0; i <= tot; i++) {
        dp[i][0] = 1;
    }
    // 从前i个数里选出j个的方案数
    for(int i = 1; i <= tot; i++) {
        int c = freqs[i - 1];
        for(int j = 1; j <= min(k, i); j++) {
            // 前i-1个数里已经选出了j个
            dp[i][j] = dp[i - 1][j];
            dp[i][j] %= MOD;
            // 前i-1个数里选出了j-1个，算上第i个数才有j个
            dp[i][j] += dp[i - 1][j - 1] * c % MOD;
            dp[i][j] %= MOD;
        }
    }
    int ans = 0;
    // 枚举非幸运数字
    for(int i = 0; i <= min(k, unlucky); i++) {
        int lucky = k - i;                // 幸运数字需要选出来的个数
        if(lucky <= tot) {
            int temp = C(unlucky, i);     // 选择非幸运数字的方案数
            temp = 1LL * temp * dp[tot][lucky] % MOD;
            ans = (ans + temp) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}