做法是折半搜索。

我第一种写法是将左半边所有的可能用 vector 记录下来，然后枚举一遍与右边的进行乘法原理。

ll ans=0; 
for(auto x:G)
{
	int num=x.first;
	ll sum=x.second;
	rep(j,0,k-num) ans=ans+(ll)mp1[num][sum]*mp2[j][S-sum];
}
printf("%lld\n",ans);

第二种写法，是对每个右半边搜索出来的结果，枚举相应的左半边的取值：

inline void dfs2(int i,int num,ll sum)
{
	if(sum>S) return;
	if(i>n)
	{
		rep(i,0,k-num) if(mp1[i].find(S-sum)!=mp1[i].end()) ans=ans+mp1[i][S-sum];
		return;
	}
	dfs2(i+1,num,sum);
	dfs2(i+1,num,sum+a[i]);
	if(check(a[i])&&num<k) dfs2(i+1,num+1,sum+fac(a[i]));
	return;
}

但是第一种写法会 WA on 4，第二种写法就没有问题，请问是为什么