题目

Source

http://acm.hdu.edu.cn/showproblem.php?pid=5800

Description

Dear Guo

I never forget the moment I met with you.You carefully asked me: "I have a very difficult problem. Can you teach me?".I replied with a smile, "of course"."I have n items, their weight was a[i]",you said,"Let‘s define f(i,j,k,l,m) to be the number of the subset of the weight of n items was m in total and has No.i and No.j items without No.k and No.l items.""And then," I asked.You said:"I want to know

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}\sum_{m=1}^{s}f(i,j,k,l,m)\quad (i,j,k,l\quad are\quad different)$$

Sincerely yours,
Liao

Input

The first line of input contains an integer T(T≤15) indicating the number of test cases.
Each case contains 2 integers n, s (4≤n≤1000,1≤s≤1000). The next line contains n numbers: a1,a2,…,an (1≤ai≤1000).

Output

Each case print the only number — the number of her would modulo 109+7 (both Liao and Guo like the number).

Sample Input

2
4 4
1 2 3 4
4 4
1 2 3 4

Sample Output

8
8

分析

题目大概就是说给n个数和s，然后求上面那个式子的结果，f(i,j,k,l,m)表示下标i和j的数必选、k和l不选且选出数的和为s的选法总数。

• dp[x][y][i][j]表示前i个数中选出总和为j且有x个数确定必选、y个数确定不选的方案数
• 转移就是选和不选从i到i+1转移，选可以向x或x+1转移，不选可以向y或y+1转移
• 最后的结果就是A(2,2)*A(2,2)*Σdp[2][2][n][0...s]

代码

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int d[3][3][1111][1111];int main(){	int t,n,s,a;	scanf("%d",&t);	while(t--){		scanf("%d%d",&n,&s);		memset(d,0,sizeof(d));		d[0][0][0][0]=1;		for(int i=0; i<n; ++i){			scanf("%d",&a);			for(int j=0; j<=s; ++j){				for(int x=0; x<3; ++x){					for(int y=0; y<3; ++y){						if(d[x][y][i][j]==0) continue;						d[x][y][i+1][j]+=d[x][y][i][j];						d[x][y][i+1][j]%=1000000007;						if(y<2){							d[x][y+1][i+1][j]+=d[x][y][i][j];							d[x][y+1][i+1][j]%=1000000007;						}						if(j+a>s) continue;						d[x][y][i+1][j+a]+=d[x][y][i][j];						d[x][y][i+1][j+a]%=1000000007;						if(x<2){							d[x+1][y][i+1][j+a]+=d[x][y][i][j];							d[x+1][y][i+1][j+a]%=1000000007;						}					}				}			}		}		long long ans=0;		for(int i=0; i<=s; ++i){			ans+=d[2][2][n][i];			ans%=1000000007;		}		ans<<=2;		ans%=1000000007;		printf("%I64d\n",ans);	}	return 0;}

HDU5800 To My Girlfriend（DP）