题目理解

我们要构造一个长度为 n 的序列 a，每个数在 0 到 m 之间。

序列的权值 = v[a₁] × v[a₂] × ... × v[aₙ]

定义 S = 2^a₁ + 2^a₂ + ... + 2^aₙ

如果 S 的二进制表示中 1 的个数 ≤ k，则序列合法。

求所有合法序列的权值和，模 998244353。

思路分析

关键点

• 每个 aᵢ 表示在 S 的二进制表示中，第 aᵢ 位上加 1
• 所以 S 的二进制中，第 p 位的值等于序列 a 中等于 p 的个数（可能有进位）

动态规划设计

我们按二进制位从低到高（0 到 m）来分配序列中的数。

定义状态： dp[i][j][c][b] =

• 已经分配了 i 个数
• 当前处理到二进制第 j 位
• 向高位的进位是 c
• 当前 S 的二进制中 1 的个数是 b

时的权值和。

转移：

• 枚举在第 j 位上选 t 个数（即 t 个位置的值 = j）
• 这一位的总和 = 进位 c + t
• 新进位 = (c + t) / 2
• 这一位的二进制值 = (c + t) % 2
• 如果这一位是 1，则 1 的个数 +1
• 权值乘上 v[j]^t，并乘组合数选择位置

代码实现

#include <iostream>
#include <cstring>
using namespace std;

const int MOD = 998244353;
int n, m, K;
int v[105];
int C[35][35];
int powv[105][35];
int dp[35][105][35][35];

// 预处理组合数和幂
void init() {
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }
    for (int i = 0; i <= m; i++) {
        powv[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            powv[i][j] = 1LL * powv[i][j-1] * v[i] % MOD;
        }
    }
}

// 计算二进制中1的个数
int popcount(int x) {
    int cnt = 0;
    while (x) {
        cnt += (x & 1);
        x >>= 1;
    }
    return cnt;
}

int main() {
    cin >> n >> m >> K;
    for (int i = 0; i <= m; i++) {
        cin >> v[i];
    }
    
    init();
    
    // 初始状态：0个数，处理第0位，进位0，1的个数0
    dp[0][0][0][0] = 1;
    
    for (int i = 0; i <= n; i++) {  // 已选数字个数
        for (int j = 0; j <= m; j++) {  // 当前处理的位
            for (int c = 0; c <= n; c++) {  // 进位
                for (int b = 0; b <= K; b++) {  // 1的个数
                    if (dp[i][j][c][b] == 0) continue;
                    
                    int val = dp[i][j][c][b];
                    // 枚举在第j位选t个数字
                    for (int t = 0; t <= n - i; t++) {
                        int total = c + t;  // 这一位的总数
                        int bit = total % 2;  // 这一位的二进制值
                        int carry = total / 2;  // 新的进位
                        int ones = b + bit;  // 新的1的个数
                        
                        if (ones > K) continue;
                        
                        // 转移：乘组合数选位置，乘v[j]^t
                        long long add = 1LL * val * C[n - i][t] % MOD;
                        add = add * powv[j][t] % MOD;
                        
                        dp[i + t][j + 1][carry][ones] = 
                            (dp[i + t][j + 1][carry][ones] + add) % MOD;
                    }
                }
            }
        }
    }
    
    // 统计答案：所有n个数字分配完毕，处理完所有位，进位展开后1的个数不超过K
    int ans = 0;
    for (int c = 0; c <= n; c++) {
        for (int b = 0; b <= K; b++) {
            if (popcount(c) + b <= K) {
                ans = (ans + dp[n][m+1][c][b]) % MOD;
            }
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

样例验证

样例1：

输入：
5 1 1
2 1
输出：
40

与题目解释一致。

复杂度分析

• 状态数：n × m × n × K ≈ 30 × 100 × 30 × 30 ≈ 2.7 × 10^6
• 可以满足题目要求

这个解法通过动态规划按位处理，同时跟踪进位和1的个数，能够高效计算出所有合法序列的权值和。