- 题目描述
给定整数 \(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\) 取模的结果。
首先我们有 \(20\) 分算法，枚举 \(a_i\) 计算并 check，复杂度大约是 \(O(n^m)\) 级别。
我们想拿到更多的分，观察数据范围发现有 \(50\) 分允许 \(2^m\) 的级别存在。
\(S\) 的范围是 \([n,n2^m]\)，我们枚举可行的 \(S\)，并判断它是否能被 \(a\) 组成，计算出贡献。可以发现这类似背包问题，我们可以选共 \(n\) 个 \(2^0\sim 2^m\) 的数组成 \(S\)。考虑倒推和记忆化搜索。因为权值可分裂，即可以表示成多个部分相乘。所以我们记 \(f[pos][sum]\) 为 \(a_i\) 的前 \(pos\) 位的组成 \(sum\) 的权值。复杂度 \(O(n2^m)\)，可以得到 \(50\) 分。
计数类问题不是组合就是 dp。
考虑 dp。
我们逐步分析 dp 状态的设计。
一般来说，这种带有数列的，一般有一维为“前 \(i\) 个数”；
并且，我们发现权值与序列顺序无关，所以元素一样的序列权值一样，我们不妨让它有序。而无序的情况可以用组合数算，也可以用总体个数除以局部个数来算。
- 组合数：已填 \(i\) 个数，接下来 \(j\) 个都填同一个值，方案数是 \(C_{n-i}^j\)；
- 阶乘：全部种类为 \(n!\)，除去每个相同的块长度的阶乘即可。
让我们很烦的一个要求就是位数小于等于 \(k\)，当 \(a_i\) 互不相同时，进位会造成很大的麻烦。
- trick：进位无后效性可以采用从低位到高位的遍历方法，并且记录第 \(i\) 位之前对其的进位数。
而每一个具有相同值的块都有边界，我们考虑枚举下一个块的长度。
记 \(f[i][j][num][p][q]\) 表示已确定 \(a\) 数组中前 \(i\) 个的取值，保证取值递增，并且取值不超过为 \(j\)，取值为 \(j\) 的块长为 \(num\)（为什么是“不超过“呢，因为这里的 \(num\) 可能为 \(0\)，我们想要的是一种前缀的形式），即 \(a_{i-num+1}\sim a_i\) 这 \(num\) 个值都为 \(j\)。而前 \(i\) 个所有的进位，我们可以分开考虑，包括 \(a_1\sim a_{i-num}\) 的值的进位以及 \(num\) 个值为 \(j\) 的进位。我们以 \(p\) 记录若是第 \(j\) 位不进位的值会是多少，方便我们接下来直接除二进位，再用 \(q\) 记录前 \(i\) 个数组成的 \(S\) 中有多少个 \(1\)。
但是，我们发现 \(num\) 似乎不用记录，只需要枚举就行了。
简单地说，\(f[i][j][p][q]\) 表示已确定前 \(i\) 位取值不超过 \(j\)，第 \(i\) 位不进位为 \(p\)，第 \(j\) 位及之前共有 \(q\) 个 \(1\)。
- 倒推不好推时，可以选用正推。
发现并不好找 \(f[i][j][p][q]\) 的组成，但我们可以考虑它对别人的贡献。
枚举 \(num\) 表示第 \(i+1\sim i+num\) 位选 \(j\)，则有：
\[f[i+num][j+1][num+\frac{p}{2}][q+(num+\frac{p}{2})\bmod 2]+=f[i][j][p][q]\times v_j^{num}\times C_{n-i}^{num} \]其中 \(i+num\) 表示已选数组 \(a\) 的前 \(i+num\) 位，并且 \(i+1\sim i+num\) 的值为 \(j+1\)，此时的进位为前 \(i\) 位贡献的 \(p\) 除以二（因为进了一位），加上又选了 \(num\) 个这一位的数。对于 \(q\)，只需要判断在此情况下 \(1\) 的个数有没有增加即可，加上 \((num+\frac{p}{2})\bmod 2\) 即可。
- 明确 dp 每个状态的取值范围
\(i\) 为 \(0\sim n\)：因为 \(i\) 更新 \(i+num\)，而 \(num\) 可能为 \(0\)；
\(j\) 为 \(0\sim m-1\)：因为 \(j\) 更新 \(j+1\)，所以只需要遍历到 \(j-1\) 即可；
\(p\) 为 \(0\sim 2n\)：但是上界应该不会到 \(2n\)。可以考虑每一位都有 \(n\) 个选同样的值，即 \(num=n\) 的极端不可能情况。但是一定要遍历够，并且空间开大！！！！！
\(q\) 为 \(0\sim k\)：上界为 \(k\) 保证 \(f[i][j][p][q]\) 是合法的再去更新；
\(num\) 为 \(0\sim n-i\)：枚举选剩下的数的个数。
当然，最后的 \(S\) 可能不止 \(m\) 位，但是添加的数最多只到第 \(m\) 位，后面不会被修改，所以后面可以不进行 dp，而是直接计算。
答案就是：
\[\sum_{p=0}^{2n}\sum_{q=0}^kf[n][m][p][q]\times[q+\rm{popcnt}(\frac{p}{2})\leq k] \]- 别忘了取模哦！
时间复杂度 \(O(n^3mk)\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
const int N=31,M=101,mod=998244353;
int n,m,k,v[M][N],f[N][M][N<<1][N],ans,C[N][N];
int popcnt(int x){
int num=0;
while(x){
x-=(x&-x),num++;
}
return num;
}
signed main(){
n=read(),m=read(),k=read();
C[0][0]=C[1][0]=C[1][1]=1;
for(int i=2;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){
v[i][1]=read();v[i][0]=1;
for(int j=2;j<=n;++j)v[i][j]=v[i][j-1]*v[i][1]%mod;
}
for(int i=0;i<=n;++i)f[i][0][i][i&1]=v[0][i]*C[n][i]%mod;
for(int i=0;i<=n;++i){
for(int j=0;j<m;++j){
for(int p=0;p<=2*n;++p){
for(int q=0;q<=k;++q){
for(int num=0;num<=n-i;++num){
f[i+num][j+1][num+p/2][q+(num+p/2)%2]=(f[i+num][j+1][num+p/2][q+(num+p/2)%2]+f[i][j][p][q]*v[j+1][num]%mod*C[n-i][num]%mod)%mod;
}
}
}
}
}
for(int p=0;p<=2*n;++p){
for(int q=0;q<=k;++q){
if(q+popcnt(p/2)<=k){
ans=(ans+f[n][m][p][q])%mod;
}
}
}
print(ans);
return 0;
}