http://acm.hdu.edu.cn/showproblem.php?pid=5800
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
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).
Each case print the only number — the number of her would modulo 109+7 (both Liao and Guo like the number).
2
4 4
1 2 3 4
4 4
1 2 3 4
8
8
题目大概就是说给n个数和s,然后求上面那个式子的结果,f(i,j,k,l,m)表示下标i和j的数必选、k和l不选且选出数的和为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; }
原文:http://www.cnblogs.com/WABoss/p/5925141.html