本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15590387.html

题目链接

首先dp得从低位向高位枚举，因为高位无论如果使用 2ai2^{a_i} 都对低位二进制1的个数无影响，满足dp的无后效性。

设 dp(k,i,x,y)dp(k, i, x, y) 为 SS 从低的高二进制的前 kk 位中，用了数列 aa 的前 ii 项，且此时 SS 中共有 xx 个二进制位为1，第 i+1i+1 位进了 yy 过去。

则：

dp(k,i,x,y)=∑j=0n−idp(k+1,i+j,x+(y+j&1),y+j>>1)×Ci+jj×vkjdp(k, i, x, y)=\sum_{j=0}^{n-i}dp(k+1, i+j, x+(y+j\&1),y+j>>1)\times C_{i+j}^j\times v_k^j

假设这一位有 jj 个 aja_j 满足 aj=ka_j=k，则下一位就有 i+ji+j 个 aa 的元素确定，如果这一位是1，则 x+1x+1，在转移中的 x+(y+j&1)x+(y+j\&1) 体现。而进位到下一位的就是 y+j>>1y+j>>1 了。

对于每种方案，其对于答案的贡献为 vkjv_k^j，而方案相当于在 i+ji+j 个数中插 jj 块板，即 Ci+jjC_{i+j}^j。

建议用记忆化搜索实现。

Code

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
// Problem: P7961 [NOIP2021] 数列【民间数据】
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7961
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define mo 998244353
#define N 40
#define M 110
int n, m, i, j, k; 
int c[M][M], s[M][M]; 
int f[M][N][N][N], v[M], K; 

int count(int x)
{
	int ans=0; 
	while(x) x-=x&-x, ++ans; 
	return ans; 
}

int dfs(int k, int u, int x, int y)
{
	if(u==n)
	{
		// printf("> f[%lld][%lld][%lld][%lld]=%lld\n", k, u, x, y, x+count(y)<=K);
		if(x+count(y)>K) return 0; 
		// printf("----------"); 
		return 1; 
	}
	if(k>m) return 0; 
	if(f[k][u][x][y]!=-1) return f[k][u][x][y]; 
	int ans=0;  
	for(int i=0; i<=n-u; ++i)
	{
		ans=(ans+dfs(k+1, u+i, x+((y+i)&1), (y+i)>>1)
						*s[k][i]%mo*c[u+i][i]%mo)%mo; 
		// printf("%lld %lld\n", s[k][i], c[n-u][i]); 
	}
	f[k][u][x][y]=ans; 
	// printf("f[%lld][%lld][%lld][%lld]=%lld\n", k, u, x, y, f[k][u][x][y]); 
	return f[k][u][x][y]; 
}


signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout); 
	memset(f, -1, sizeof(f)); 
	n=read(); m=read(); K=read(); 
	for(i=0; i<=m; ++i) v[i]=read(); 
	c[0][0]=1; 
	for(i=1; i<=n; ++i)
		for(j=c[i][0]=1; j<=i; ++j) 
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo; 
	for(i=0; i<=m; ++i)
	{
		s[i][0]=1; 
		for(j=1; j<=n; ++j) s[i][j]=(s[i][j-1]*v[i])%mo; 
	}
	printf("%lld\n", dfs(0, 0, 0, 0)); 
	return 0;
}