母函数水过
#include<stdio.h> #include<string.h> #define lmax 10000 int c1[lmax+1],c2[lmax+1]; int main() { int n,i,j,k,t,a[25],sum,b; scanf("%d",&t); while(t--) { sum=0; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); sum=sum+a[i]; } for(k=1;k<=n;k++) { for (i=0;i<=sum;i++) { c1[i]=0; c2[i]=0; } c1[a[k]]=1; for (i=1;i<=n;i++) { if(i==k)continue; for (j=0;j<=sum;j++) { c2[j]+=c1[j]; c2[j+a[i]]+=c1[j]; } for (j=0;j<=sum;j++) { c1[j]=c2[j]; c2[j]=0; } } b=0; for(i=sum/2+1;i<=sum;i++) if(i-a[k]<sum/2+1) b=b+c1[i]; if(k==1) printf("%d",b); else printf(" %d",b); } printf("\n"); } return 0; }