思路与算法

从二进制低位到高位处理指数i。状态记录已分配位置数u、由低位传来的进位c、已确定的1位数b。选t个尚未分配的位置赋值为i，贡献乘C(n-u,t)*v_i^t；当前位为(c+t)%2，进位为(c+t)/2。处理0..m后，把剩余进位的popcount加入b，满足≤k的状态累加。组合数用Pascal递推预处理。

正确性说明

一个有序指数序列按每个指数出现在哪些位置可唯一分组；每一步组合数恰选择这些位置，不重不漏，乘积权值也逐项相同。低位进位完全由c与本位出现数t决定，已确定的位不会被高位修改，故状态足够。收尾进位仍可能有1，计入后正好是S的全部1数。全部转移模质数运算保持所求余数。

复杂度

含组合数、幂表与滚动数组初始化，保守O((m+1)n^4)时间、O(n³+mn)空间；n≤30。

易错点

指数允许0，m也允许0。序列有顺序，不能漏组合数；最后进位不是仅加1，而是加其全部二进制1数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    const long long MOD = 998244353;
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> v(m + 1);
    for (auto &x : v)
        cin >> x;
    long long C[31][31] = {};
    C[0][0] = 1;
    for (int i = 1; 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;
    }
    int W = n + 1;
    vector<long long> d(W * W * W), e(d.size());
    auto idx = [&](int used, int carry, int ones) {
        return (used * W + carry) * W + ones;
    };
    d[idx(0, 0, 0)] = 1;
    for (long long value : v) {
        fill(e.begin(), e.end(), 0);
        vector<long long> power(W, 1);
        for (int z = 1; z <= n; z++)
            power[z] = power[z - 1] * value % MOD;
        for (int used = 0; used <= n; used++)
            for (int carry = 0; carry <= n; carry++)
                for (int ones = 0; ones <= k; ones++)
                    if (d[idx(used, carry, ones)])
                        for (int take = 0; used + take <= n; take++) {
                            int sum = carry + take, newones = ones + (sum & 1);
                            if (newones > k)
                                continue;
                            long long &out = e[idx(used + take, sum / 2, newones)];
                            out = (out + d[idx(used, carry, ones)] * C[n - used][take] % MOD *
                                             power[take]) %
                                  MOD;
                        }
        d.swap(e);
    }
    long long ans = 0;
    for (int c = 0; c <= n; c++)
        for (int b = 0; b <= k; b++)
            if (b + __builtin_popcount((unsigned)c) <= k)
                ans = (ans + d[idx(n, c, b)]) % MOD;
    cout << ans << "\n";
}