母函数水过
#include<stdio.h> #include<string.h> int main() { int i,j,n,c1[50],c2[50],a[10],b[10],h,K,t; scanf("%d",&t); while(t--) { scanf("%d%d",&K,&n); for(i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]); memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); c1[0]=1; for(i=0;i<n;i++) { for(j=0;j<=K;j++) for(h=0;h<=b[i]&&h*a[i]+j<=K;h++) c2[j+h*a[i]]+=c1[j]; for(j=0;j<=K;j++) {c1[j]=c2[j];c2[j]=0;} } printf("%d\n",c1[K]); } return 0; }