题目链接
由于 \(M\) 很大且是完全背包，可以考虑二进制分组，把物品 \(a _ i\) 拆成体积为 \(2 ^ 0 a _ i, 2 ^ 1 a _ i, 2 ^ 2 a _ i, \ldots\) 的物品，转化成 01 背包问题。
先考虑 \(2 ^ 0 a _ i\) 的那些物品，可以跑一遍 01 背包计算出 \(f _ i\) 表示体积之和为 \(i\) 的方案数，然后因为后面物品的体积都是 \(2\) 的倍数，所以可以把剩余体积 \(M - i\) 二进制下最后一位删掉。具体地，令 \(g _ i\) 为下一阶段的初始状态，有
-
\(M\) 为奇数：\(f _ i \rightarrow g _ {\lfloor i / 2 \rfloor}\)
-
\(M\) 为偶数：\(f _ i \rightarrow g _ {\lceil i / 2 \rceil}\)
然后令 \(M \leftarrow \lfloor M / 2 \rfloor\)，继续做 \(2 ^ 1 a _ i, 2 ^ 2 a _ i, \ldots\) 即可。最终答案为 \(f _ 0\)。
#include<cstdio>
#include<cstring>
#define N 105
#define V 20005
using namespace std;const int mod=998244353,lgm=60,v=2e4;
int n,a[N],f[V],g[V];
long long m;
void add(int &x,long long y) {x=(x+y)%mod;}
int main() {scanf("%d%lld",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);f[0]=1;for(int i=0;i<lgm;i++) {for(int j=1;j<=n;j++)for(int k=v;k>=a[j];k--)add(f[k],f[k-a[j]]);memset(g,0,sizeof(g));for(int k=0;k<=v;k++)if(m>>i&1) add(g[k/2],f[k]);else add(g[(k+1)/2],f[k]);memcpy(f,g,sizeof(f));}printf("%d\n",f[0]);return 0;
}