DP
状态设计
为了便于处理，称二进制最低位为第 $0$ 位（权值位 $2^0$）。
考虑从小到大填入 $a_i$。
设 $dp_{i,j,k,l}$ 表示处理了 $a_1\sim a_i$，$S$ 能进位到的最高位为 $2^j$（实际上最高位也可以不是 $2^j$，之前的 $a_i$ 最大值为 $j-1$），最高位 $2^j$ 有 $k$ 个，已知 $l$ 位为 $1$ 的答案。
则答案为：
\[\sum_{\operatorname{count}(k)+l\leq K}dp_{n,m+1,k,l}\]其中，$\operatorname{count}(k)$ 表示 $k$ 在二进制下 $1$ 的个数。
状态转移
不好从其他状态转移到 $dp_{i,j,k,l}$，那就考虑从 $dp_{i,j,k,l}$ 向外转移。
假设再往 $a$ 中填入 $t$ 个 $j$，则有：
\[dp_{i+t,j+1,\left\lfloor\frac{k+t}{2}\right\rfloor,l+(k+t)\bmod 2}\leftarrow dp_{i+t,j+1,\left\lfloor\frac{k+t}{2}\right\rfloor,l+(k+t)\bmod 2}+dp_{i,j,k,l}\cdot v_j^t\cdot \binom{i+t}{t}\]再往 $a$ 中填入 $t$ 个 $j$，则之后一共有 $i+t$ 个；$S$ 进位到了第 $j+1$ 位；$\left\lfloor\dfrac{k+t} {2}\right\rfloor$ 表示向下一位进的 $1$ 的个数；$l+(k+t)\bmod 2$ 是进位后剩下的没有进位的 $1$ 与原来的 $2^0\sim 2^{j-1}$ 的 $l$ 个 $1$ 的总共的数量。
然后再乘上一个组合数即可，从 $i+t$ 个中选择 $t$ 个填入。
边界条件
\[dp_{0,0,0,0}=1\]AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<unordered_map>
using namespace std;
constexpr const int N=30,M=100,K=N,P=998244353;
int n,m,kk,v[M+1];
int dp[N+1][M+1+1][N+1][K+1];
int qpow(int a,int n){
int base=a,ans=1;
while(n){
if(n&1){
ans=1ll*ans*base%P;
}
base=1ll*base*base%P;
n>>=1;
}
return ans;
}
int C(int n,int m){
static int mem[N+M+1][N+1];
if(n<m){
return 0;
}
if(m==0||m==n){
return 1;
}
if(mem[n][m]){
return mem[n][m];
}
return mem[n][m]=(1ll*C(n-1,m)+C(n-1,m-1))%P;
}
int count(int x){
int ans=0;
while(x){
if(x&1){
ans++;
}
x>>=1;
}
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>kk;
for(int i=0;i<=m;i++){
cin>>v[i];
}
dp[0][0][0][0]=1;
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=n;k++){
for(int l=0;l<=kk;l++){
if(dp[i][j][k][l]){
for(int t=0;i+t<=n;t++){
int &pl=dp[i+t][j+1][k+t>>1][l+(k+t&1)];
pl=(1ll*pl+1ll*dp[i][j][k][l]*qpow(v[j],t)%P*C(i+t,t)%P)%P;
}
}
}
}
}
}
int ans=0;
for(int k=0;k<=n;k++){
for(int l=0;l<=kk;l++){
if(count(k)+l<=kk){
ans=(1ll*ans+dp[n][m+1][k][l])%P;
}
}
}
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
/*
8 9 4
934258593 150407625 187068439 162292791 219945760 512449588 803393963 983648121 484675481 412407699
642171527
*/
