题解：组合数学计数+乘法原理

每一种原料出现次数都必须要是$k$的整数倍，因此其出现的次数就一定是$0,k,2k,...,mk$ 设第$i$种原料的总个数为$a_i$，我们可以使用组合计数去枚举选择的方案数$c_i=C(a_i,0)+C(a_i,k)+C(a_i,2k)+...$ 然后根据乘法原理可知，总的选择方案数就一定为所有原料选择的方案数累乘 即$(\prod_{i=1}^{50}c_i)-1$ 减1，是因为不能一种原料都不选，因为题目要求是非空子序列，因此需要把总的计算结果减去1。

C++

#include<bits/stdc++.h>
using namespace std;
const int N=1E5+10,mod=1E9+7;
long long n,w[N],k;
unordered_map<int,int>cnts;  //统计每一种糖果出现的次数
long long fac[N], ifac[N];  //阶乘和阶乘的逆元
long long qmi(long long a, long long b,int MOD) {  //快速幂
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
long long Comb(int a, int b,int mod) {  //求C(a,b)的组合数
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}
int main()
{
    cin>>n>>k;
    fac[0] = ifac[0] = 1;  //阶乘和阶乘对应的逆元初始化
    for (int i = 1; i <=n; i++) {  //预处理阶乘和阶乘的逆元
        fac[i] = fac[i - 1] * i % mod;
        ifac[i]=ifac[i-1]*qmi(i,mod-2,mod)%mod;
    }
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        cnts[x]++;
    }
    long long res=1;
    for(auto &candy:cnts)   //枚举第i种糖果选0个 k个 2k个 ...
    {
        int v=candy.second;
        if(v<k)continue;
        long long s=0;
        for(int i=0;i<=v;i+=k){
            s=(s+Comb(v,i,mod))%mod;  //计算组合数
        }
        res=(res*s)%mod;
    }
    res=(res-1);  //去除空集的情况
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static final int N = (int)1E5+10, MOD = (int)1E9+7;
    static long[] fac = new long[N], ifac = new long[N];  // 阶乘和阶乘的逆元
    static Map<Integer, Integer> cnts = new HashMap<>();  // 统计每一种糖果出现的次数

    // 快速幂
    static long qmi(long a, long b) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = res * a % MOD;
            }
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }

    // 求C(a,b)的组合数
    static long Comb(int a, int b) {
        return fac[a] * ifac[b] % MOD * ifac[a - b] % MOD;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt();
        fac[0] = ifac[0] = 1;  // 阶乘和阶乘对应的逆元初始化
        for (int i = 1; i <= n; i++) {  // 预处理阶乘和阶乘的逆元
            fac[i] = fac[i - 1] * i % MOD;
            ifac[i] = ifac[i - 1] * qmi(i, MOD - 2) % MOD;
        }
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            cnts.put(x, cnts.getOrDefault(x, 0) + 1);
        }
        long res = 1;
        for (Map.Entry<Integer, Integer> candy : cnts.entrySet()) {  // 枚举第i种糖果选0个 k个 2k个 ...
            int v = candy.getValue();
            if (v < k) continue;
            long s = 0;
            for (int i = 0; i <= v; i += k) {
                s = (s + Comb(v, i)) % MOD;  // 计算组合数
            }
            res = (res * s) % MOD;
        }
        res = (res - 1);  // 去除空集的情况
        System.out.println(res);
    }
}

Python

MOD = 10**9 + 7
N = 10**5 + 10
fac = [0]*N
ifac = [0]*N
cnts = {}  # 统计每一种糖果出现的次数

# 快速幂
def qmi(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

# 求C(a,b)的组合数
def Comb(a, b):
    return fac[a] * ifac[b] % MOD * ifac[a - b] % MOD

n, k = map(int, input().split())
fac[0] = ifac[0] = 1  # 阶乘和阶乘对应的逆元初始化
for i in range(1, n+1):  # 预处理阶乘和阶乘的逆元
    fac[i] = fac[i - 1] * i % MOD
    ifac[i] = ifac[i - 1] * qmi(i, MOD - 2) % MOD
w=list(map(int,input().split()))
for x in w:
    if x in cnts:
        cnts[x] += 1
    else:
        cnts[x] = 1

res = 1
for v in cnts.values():  # 枚举第i种糖果选0个 k个 2k个 ...
    if v < k: continue
    s = 0
    for i in range(0, v+1, k):
        s = (s + Comb(v, i)) % MOD  # 计算组合数
    res = (res * s) % MOD

res = (res - 1)  # 去除空集的情况
print(res)