P8565 100pts link 546ms

#include<bits/stdc++.h>
#include <fstream>
#include <iostream>
using namespace std;
#define LL long long
map<long long,int>dp[157]; 
const int maxn=157;
const int mod=998244353;
const long long mx=1e18;
long long a[maxn],s[maxn],x;
int q,m,cnt;
inline int dfs(long long sum,int last){
	if(dp[last].find(sum)!=dp[last].end()) return dp[last][sum]; 
	if(sum<0) return 0;
	if(!last) return (sum?0:1);
	/*for(register int i=last;i>=1;i--){
		if(sum-s[i]>0) break;
		if(sum-a[i]>=0) ans+=dfs(sum-a[i],i-1);
	}*/
	if(sum-s[last]>0) return 0;
	return dp[last][sum]=(dfs(sum,last-1)+dfs(sum-a[last],last-1))%mod;
}
signed main(){
	int T;
	cin>>T;
	while(T--){
		cin>>m>>q;
		for(register int i=1;i<=m;i++) cin>>a[i];
		for(cnt=m+1;1;cnt++){
			bool flag=0;
			a[cnt]=0;
			for(register int j=1;j<=m;j++){
				a[cnt]+=a[cnt-j];
				if(a[cnt]>mx){
					flag=1;
					break;
				}
			}
			if(flag) break;
		}
		cnt--;
		for(register int i=1;i<=cnt;i++) s[i]=s[i-1]+a[i],dp[i].clear();
		while(q--){
			cin>>x;;
			cout<<dfs(x,cnt)<<'\n';
		}
	}
	return 0;
}

90ptslink

4.04s

#include<bits/stdc++.h>
using namespace std;
#define LL long long
map<long long,int>dp[157]; 
const int maxn=157;
const int mod=998244353;
const long long mx=1e18;
long long a[maxn],s[maxn],x;
int q,m,cnt;
#define ww(x,c) write(x),putc(c),flush()
namespace IO{
	int len = 0;
	char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin),(iS == iT ? EOF : *iS++) : *iS++)
	#define reg register
	inline long long read(){
		reg char ch(gh());
		reg long long x(0);
		reg char t=0;
		while(!isdigit(ch)) t|=ch=='-',ch=gh();
		while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch&15),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch)
	{
		out[len++] = ch;
	}
	template <class T> inline void write(T x)
	{
		if (x < 0)
			putc('-'), x = -x;
		if (x > 9)
			write(x / 10);
		out[len++] = x % 10 + 48;
	}
	inline void flush()
	{
		fwrite(out, 1, len, stdout);
		len = 0;
	}
}using IO::read;
using IO::write;
using IO::putc;
using IO::flush;

int dfs(long long sum,int last){
	if(dp[last].find(sum)!=dp[last].end()) return dp[last][sum];
	if(!sum) return 1;
	long long ans=0;
	for(register int i=last;i>=1;i--){
		if(sum-s[i]>0) break;
		if(sum-a[i]>=0) ans+=dfs(sum-a[i],i-1);
	}
	return dp[last][sum]=ans%mod;
}
signed main(){
	int T;
	T=read();
	while(T--){
		m=read(),q=read();
		for(register int i=1;i<=m;i++) a[i]=read();
		for(cnt=m+1;1;cnt++){
			bool flag=0;
			a[cnt]=0;
			for(register int j=1;j<=m;j++){
				a[cnt]+=a[cnt-j];
				if(a[cnt]>mx){
					flag=1;
					break;
				}
			}
			if(flag) break;
		}
		cnt--;
		for(register int i=1;i<=cnt;i++) s[i]=s[i-1]+a[i],dp[i].clear();
		while(q--){
			x=read();
			ww(dfs(x,cnt),'\n');
		}
	}
	return 0;
}