题面

给定整数 ​n, m, k，和一个长度为 ​m + 1 的正整数数组 ​v_0, v_1, \ldots, v_m。

对于一个长度为 ​n，下标从 ​1 开始且每个元素均不超过 ​m 的非负整数序列 ​\{a_i\}，我们定义它的权值为 ​v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}。

当这样的序列 ​\{a_i\} 满足整数 ​S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n} 的二进制表示中 ​1 的个数不超过 ​k 时，我们认为 ​\{a_i\} 是一个合法序列。

计算所有合法序列 ​\{a_i\} 的权值和对 ​998244353 取模的结果。

【数据范围】

对所有测试点保证 ​1 \leq k \leq n \leq 30，​0 \leq m \leq 100，​1 \leq v_i < 998244353。

大意

有​m+1种数，分别为​2^i(0 \le i \le m)，每种数有一个权值。每个数可多次选，一共选​n个，设这些数加起来的和为​S，要求​popcount(S) \le K。若按选择顺序构成的序列不同，则认为是不同方案。对于一种方案，其权值为所选数的权值的乘积。求所有可行方案的权值和。

分析

假设当前在选二进制下第​i位为​1的数，即​2^i，选了​k个，则当前二进制位会向更高一位的二进制位进位​\frac{k}{2}。

当前位还可能接受来自更低一位的进位，设该进位值为​p，则最终​S当前位为​(p+k) \bmod 2，当前位会向更高位进位​\lfloor\frac{p+k}{2}\rfloor。

进位只可能向更高位进位，所以进位并不会改变当前位及更低位的​1的个数，即从低位向高位枚举每一位是没有后效性的。

现在可以考虑DP了。

算法

设计DP状态。考虑需要记录哪些值。

  • 显然需要记录当前在处理二进制下哪一位；
  • 总共只能选​n个数，需要记录现在已经选了几个数；
  • 要求​popcount(S) \le K，需要记录当前位及更低位已经有了几个​1；
  • 向更高一位的进位会对后面DP造成影响，需要将进位的值记录在状态中。

因此，设DP状态​f[i][j][k][p]表示当前已处理完二进制的第​i位，已经选了​j个数，当前位及更低位已经有了​k个​1，当前位会向更高一位进位​p，所有可行方案的权值和。

因为选择序列不同被认为是不同方案，即交换序列中两个不同元素会产生新的方案，我们在转移时需加以考虑。
假设选择序列中已经确定了​j个位置（无需考虑是哪​j个位置，因为无论是哪​j个位置后续的选择方案数都是相同的），那么还有​n-j个位置没有确定，假设现在要选​t个相同的数，那么现在有​\binom{n-j}{t}个选择方案。向当前状态转移的所有方案都可以与这​\binom{n-j}{t}个方案组合，体现在权值上就是之前每种方案的的权值都贡献了​\binom{n-j}{t}次。对于每种方案，当前数的权值贡献是​v_i^t。因此，转移时乘上​\binom{n-j}{t}v_i^t的系数即可。

转移方程如下：

f[i][j][k][p] \times \binom{n-j}{t}v_{i+1}^t \rarr f[i+1][j+t][k+((p+t) \bmod 2)][\lfloor\frac{p+t}{2}\rfloor]

​i计算到​m就停止，因为后面已经没法再选数了，后面的位已经由第​m位的进位确定了。

最后统计答案。假设第​m位向更高位进位​p，那么更高位就一共有​popcount(p)个​1。要求​popcount(S) \le K，因此答案只统计​popcount(p)+k \le K的状态。

ans=\sum_{1 \le k \le K,0 \le p \le \lfloor\frac{n}{2}\rfloor,popcount(p)+k \le K}f[m][n][k][p]

时间复杂度

枚举状态​O(n^3 m)，转移​O(n)，总时间复杂度​O(n^4 m)。

代码（未卡常）

#include <bits/stdc++.h>
struct FastIO{...}; // 快读快写
using namespace std;
using ll=long long;
const int N=30,M=100,mod=998244353;
inline ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;}
ll fact[N+1],inv[N+1];
inline void pre(){fact[0]=1;inv[0]=1;for(int i=1;i<=N;i++) fact[i]=fact[i-1]*i%mod,inv[i]=qpow(fact[i],mod-2);}
inline ll C(int n,int m){return fact[n]*inv[n-m]%mod*inv[m]%mod;}
int n,m,K;
ll ans;
int V[M+1];
ll f[M+1][N+1][N+1][N+1];
inline void DP(){
    for(int t=0;t<=n;t++){f[0][t][t&1][t/2]=qpow(V[0],t)*C(n,t)%mod;}
    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;p++){
                    for(int t=0;t<=n-j;t++){
                        f[i+1][j+t][k+((t+p)&1)][(p+t)/2]+=f[i][j][k][p]*C(n-j,t)%mod*qpow(V[i+1],t)%mod;
                    }
                }
            }
        }
    }
    for(int i=0;i<=K;i++){
        for(int j=0;j<=n/2;j++){
            if(__builtin_popcount(j)+i>K) continue;
            (ans+=f[m][n][i][j])%=mod;
        }
    }
}
int main(){
    FastIO io;
    pre();
    io>>n>>m>>K;
    for(int i=0;i<=m;i++) io>>V[i];
    DP();
    io<<ans;
    return 0;
}