背包变形。dp[i][j][g][h]表示前i个数字，和为j，有g个必选，有h个必不选的方案数。
答案为sum{dp[n][j][2][2]}*4
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=1000+10; int dp[maxn][maxn][3][3],f[maxn][maxn][3][3]; int mod=1e9+7; int T,n,s,a[maxn]; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) scanf("%d",&a[i]); memset(dp,0,sizeof dp); dp[0][0][0][0]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=s;j++) { for(int p=0;p<=2;p++) { for(int h=0;h<=2;h++) { int num=0; num=(num+dp[i-1][j][p][h])%mod; if(j-a[i]>=0) num=(num+dp[i-1][j-a[i]][p][h])%mod; if(p-1>=0&&j>=a[i]) num=(num+dp[i-1][j-a[i]][p-1][h])%mod; if(h-1>=0) num=(num+dp[i-1][j][p][h-1])%mod; dp[i][j][p][h]=num; } } } } LL ans=0; for(int i=1;i<=s;i++) ans=(ans+dp[n][i][2][2])%mod; printf("%lld ",(ans*4)%(LL)mod); } return 0; }