题解

题目描述

给定一个由 $n$ 个正整数构成的数组 $\{a_1,a_2,\dots,a_n\}$，要求从中选择至多 $k$ 个数， 使得这些数的乘积恰好为 $p$ 的倍数。
输入时，第一行给出正整数 $n,k,p$（其中 $1\le n,p\le 100$ 且 $1\le k\le n$），代表数组的元素数量、最多可以挑选的元素个数以及倍数 $p$；第二行给出 $n$ 个正整数 $a_1,a_2,\dots,a_n$（每个 $a_i$ 满足 $1\le a_i\le 10^9$）。
输出时，将满足条件的选数方案总数对 $10^9+7$ 取模后输出。

题目思路

题目要求选取的数的乘积必须为 $p$ 的倍数，即其乘积可以被 $p$ 整除。注意到：

• 如果 $p=1$，那么任何数的乘积均为 $1$ 的倍数，此时方案数即所有选取个数不超过 $k$ 的子集数（包括空集）。
• 对于 $p>1$，我们要求乘积 $\prod \text{选中的数字} \equiv 0 \pmod{p}$。

由于 $n$、$k$ 和 $p$ 都很小（最多 $100$），可以采用动态规划（DP）方法解决。

DP 状态定义

设 $dp[i][j][r]$ 表示前 $i$ 个数中选取 $j$ 个数，且这些数的乘积对 $p$ 取余结果为 $r$ 的方案数。

• 初始状态：$dp[0][0][1 \bmod p] = 1$（空集的乘积定义为 $1$，注意空集只有在 $p=1$ 时满足条件，但在转移中仍需初始化）。
• 状态转移：
  1. 不选第 $i$ 个数：则 $dp[i][j][r]$ 的方案数会传递到 $dp[i+1][j][r]$。
  2. 选第 $i$ 个数：设当前 $a_{i+1}$ 取值为 $x$，那么新的余数为 $(r * x) \bmod p$，同时选数个数增加 $1$。

最后答案为

即选择任意个数（最多 $k$ 个）后乘积余 $p$ 等于 $0$ 的方案数。

C++

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;

int main(){
    int n, k, p;
    cin >> n >> k >> p;
    vector<int> a(n);
    for (int i=0; i<n; i++){
        cin >> a[i];
    }
    // 初始化三维DP数组，dp[i][j][r]表示前i个数字中选择j个，乘积模p余数为r的方案数
    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(p, 0)));
    // 空集的乘积默认为1，因此余数为 (1 % p)
    dp[0][0][1 % p] = 1;

    for (int i=0; i<n; i++){
        for (int j=0; j<=k; j++){
            for (int r=0; r<p; r++){
                if(dp[i][j][r] != 0){
                    // 不选第i个数字，状态不改变
                    dp[i+1][j][r] = (dp[i+1][j][r] + dp[i][j][r]) % MOD;
                    // 如果还能选数字，则选择第i个数字
                    if(j + 1 <= k){
                        int newR = (int)((1LL * r * (a[i] % p)) % p);
                        dp[i+1][j+1][newR] = (dp[i+1][j+1][newR] + dp[i][j][r]) % MOD;
                    }
                }
            }
        }
    }

    // 答案为所有选择个数不超过k的方案中乘积余数为0的方案和
    int ans = 0;
    for (int j=0; j<=k; j++){
        ans = (ans + dp[n][j][0]) % MOD;
    }
    cout << ans << endl;
    return 0;
}

Python

MOD = 10**9 + 7

def main():
    import sys
    input_data = sys.stdin.read().split()
    # 读取输入，n, k, p分别代表数字个数、最多选择个数、倍数p
    n = int(input_data[0])
    k = int(input_data[1])
    p = int(input_data[2])
    a = list(map(int, input_data[3:3+n]))
    
    # 初始化dp数组，dp[i][j][r]表示前i个数字中选取j个，乘积模p余数为r的方案数
    dp = [[[0] * p for _ in range(k+1)] for __ in range(n+1)]
    dp[0][0][1 % p] = 1  # 空集乘积定义为1
    
    for i in range(n):
        for j in range(k+1):
            for r in range(p):
                if dp[i][j][r]:
                    # 不选当前数字
                    dp[i+1][j][r] = (dp[i+1][j][r] + dp[i][j][r]) % MOD
                    # 选当前数字，如果还未达到选择数量上限
                    if j + 1 <= k:
                        new_r = (r * (a[i] % p)) % p
                        dp[i+1][j+1][new_r] = (dp[i+1][j+1][new_r] + dp[i][j][r]) % MOD
    
    # 累加所有选择个数不超过k的方案中，余数为0的个数
    ans = 0
    for j in range(k+1):
        ans = (ans + dp[n][j][0]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Java

import java.util.*;
import java.io.*;

public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        // 利用BufferedReader读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split("\\s+");
        int n = Integer.parseInt(params[0]);
        int k = Integer.parseInt(params[1]);
        int p = Integer.parseInt(params[2]);
        
        String[] numStr = br.readLine().split("\\s+");
        int[] a = new int[n];
        for (int i=0; i<n; i++){
            a[i] = Integer.parseInt(numStr[i]);
        }
        
        // dp[i][j][r]表示前i个数字中选取j个数字，乘积模p余数为r的方案数
        int[][][] dp = new int[n+1][k+1][p];
        dp[0][0][1 % p] = 1;  // 空集的乘积默认为1
        
        // 状态转移
        for (int i = 0; i < n; i++){
            for (int j = 0; j <= k; j++){
                for (int r = 0; r < p; r++){
                    if(dp[i][j][r] != 0){
                        // 不选第i个数字
                        dp[i+1][j][r] = (dp[i+1][j][r] + dp[i][j][r]) % MOD;
                        // 如果还可以选数字，则选第i个数字
                        if(j + 1 <= k){
                            int newR = (int)(((long)r * (a[i] % p)) % p);
                            dp[i+1][j+1][newR] = (dp[i+1][j+1][newR] + dp[i][j][r]) % MOD;
                        }
                    }
                }
            }
        }
        
        // 累加所有选择个数不超过k的方案中乘积余数为0的方案数
        int ans = 0;
        for (int j = 0; j <= k; j++){
            ans = (ans + dp[n][j][0]) % MOD;
        }
        System.out.println(ans);
    }
}

题目内容

对于给定的由$n$个正整数构成的数组 {$a_1,a_2,…,a_n$} ,从中选择至多 $k$ 个数,使得这些数的乘积恰好为 $p$ 的倍数。

小美想知道，一共有多少种满足条件的选数方案？由于答案可能很大,请将答案对 $(10^9+7)$ 取模后输

输入描述

第一行输入三个正整数 $n,k,p(1≦n,p≦100;1≦k≦n)$ 代表数组中的元素数量、至多挑选的元素数量,位期的涨取用

第二方输入 $n$ 个正整数 $a_1，a_2,...,a_n(1≤a_i≤10^9)$ 代表教组中的元素。

输出描述

在一行上输出一个整数，代表满足条件的选数方案。由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

样例1

输入

5 5 30
1 2 3 4 5

输出

6