分析：首先定义状态dp[i][j][s1][s2]代表前i个物品中，选若干个物品，总价值为j
其中s1个物品时必选，s2物品必不选的方案数
那么转移的时候可以考虑，第i个物品是可选可可不选的
- dp[i][j][s1][s2]+=dp[i-1][j][s1][s2]+dp[i-1][j-a[i]][s1][s2]
或者第i个物品必选，或者必不选
- dp[i][j][s1][s2]+=dp[i-1][j-a[i]][s1-1][s2]+dp[i-1][j][s1][s2-1]
一点感想：这个题边界时dp[0][0][0][0]=1；
当i不等于0时，dp[i][0][s1][s2]也是有意义的，因为可以代表s2个物品必不选，所以从0开始
由于空间是O(9E6)的，太大，类似01背包优化成一维O(9e3)
时间复杂度O(N*S*9)(发现又是一道计数dp，一般涉及计数的dp不是特别好做，主要是人傻)
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e3+;
const int mod = 1e9+;
int dp[N][][];
int a[N],T,n,s;
inline void up(int &x,int y){
x+=y;if(x>=mod)x-=mod;
}
inline int mul(int x,int y){
int ret=(1ll*x*y)%(1ll*mod);
return ret;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&s);
for(int i=;i<=n;++i)scanf("%d",&a[i]);
memset(dp,,sizeof(dp));
dp[][][]=;
for(int i=;i<=n;++i)
for(int j=s;j>=;--j)
for(int s1=;s1>=;--s1)
for(int s2=;s2>=;--s2){
int tmp=;
up(tmp,dp[j][s1][s2]);
if(j>=a[i])up(tmp,dp[j-a[i]][s1][s2]);
if(s1&&j>=a[i])up(tmp,dp[j-a[i]][s1-][s2]);
if(s2)up(tmp,dp[j][s1][s2-]);
dp[j][s1][s2]=tmp;
}
int ret=;
for(int i=;i<=s;++i)up(ret,dp[i][][]);
ret=mul(ret,);
printf("%d\n",ret);
}
return ;
}