这题想了一半，后面有点不敢想结果直接看题解了。
思考后发现，对于 \(a_i\le x\)，也就是二进制中第 \(x\) 位前的部分，它们都可能会影响到二进制中第 \(x\) 位后的进位，而 \(a_i>x\) 的部分是不会影响到 \(x\) 位前的进位的。
所以为了满足无后效性，我们从低位向高位考虑，这样之后的答案对之前的答案没有影响。
设 \(dp(i,j,k,p)\) 为已经考虑完了前 \(i-1\) 位，已经用了 \(j\) 个 \(a_i\)，前 \(i-1\) 位中有 \(k\) 个 \(1\)，并且进位到第 \(i\) 为 \(p\) 个 \(1\) 的合法序列权值和。
考虑向后转移更简单，由于乘法分配律，
\((g_1+g_2+\cdots+g_l)\times v_i=g_1\times v_i+g_2\times v_i+\cdots+g_l\times v_i\)
\(g_i\) 表示当前的合法方案，所以当前权值和是可以通过先前权值和成当前位的权值得来。
考虑再枚举 \(t\) 表示第 \(i\) 位用了 \(t\) 个 \(a_i\)，所以
\(dp(i+1,j+t,k+(t+p)\bmod2,\lfloor\frac{t+p}{2}\rfloor)\leftarrow dp(i,j,k,p)\times v_i^t\times \tbinom{n-j}{r}\)
组合数是因为 \(t\) 个 \(a_i\) 可以放在剩下 \(n-j\) 个位置的任意位置。
答案即为 \(\sum dp(m+1,n,k,p)\)，满足 \(k+popcnt(p)\le K\)，\(popcnt(p)\) 计算的是第 \(m\) 位之后的进位。
复杂度为 \(O(n^4m)\)。
总结：无后效性的转移，状态表示，不同方案之间的转移满足分配律，贡献的计算。
#include <bits/stdc++.h>
typedef long long ll;
ll read() {
ll x = 0, f = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') f = -1;
c = getchar();
}
while(isdigit(c)) {
x = (x << 3) + (x << 1) + (c - '0');
c = getchar();
}
return x * f;
}
ll n, m, K, mod = 998244353;
ll v[100010], c[40][40], pw[110][40], dp[110][32][32][55];
void init() {
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] + c[i - 1][j - 1]) % mod;
}
}
}
ll popcnt(ll x) {
ll cnt = 0;
while(x) {
cnt += (x & 1);
x >>= 1;
}
return cnt;
}
void Solve() {
n = read(), m = read(), K = read();
init();
for(int i = 0; i <= m; i++) {
v[i] = read();
pw[i][0] = 1;
for(int j = 1; j <= n; j++) pw[i][j] = pw[i][j - 1] * v[i] % mod;
}
dp[0][0][0][0] = 1;
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
for(int k = 0; k <= K; k++) {
for(int p = 0; p <= (n >> 1); p++) {
for(int t = 0; t <= n - j; t++) {
dp[i + 1][j + t][k + (t + p) % 2][(t + p) / 2] = (dp[i + 1][j + t][k + (t + p) % 2][(t + p) / 2] + dp[i][j][k][p] * pw[i][t] % mod * c[n - j][t] % mod) % mod;
// std::cout << dp[i + 1][j + t][k + (t + p) % 2][(t + p) / 2] << "\n";
}
}
}
}
}
ll ans = 0;
for(int k = 0; k <= K; k++) {
for(int p = 0; p <= (n >> 1); p++) {
if(k + popcnt(p) <= K) ans = (ans + dp[m + 1][n][k][p]) % mod;
}
}
std::cout << ans << "\n";
}
int main() {
Solve();
return 0;
}