串联电阻
高精+完全背包
核心
for(int i=1;i<=n;++i) for(int j=1;j<=mt;++j) if(j-v[i]>=0) ans[j]=ans[j]+ans[j-v[i]];
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 #define rg register 5 const int base=10000,power=4; 6 const int N=30; 7 ll n,v[N],tt,t[2005],mt;int cnt; 8 template<class t>void rd(t &x) 9 { 10 x=0;int w=0;char ch=0; 11 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 12 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 13 x=w?-x:x; 14 } 15 struct node{ 16 int a,b,c; 17 bool operator <(const node x) const{return c<x.c;} 18 }e[N]; 19 20 struct num{ 21 int a[100]; 22 num(){memset(a,0,sizeof(a));} 23 num(int x) 24 { 25 memset(a,0,sizeof(a)); 26 int t=0; 27 while(x) 28 { 29 a[++t]=x%base; 30 x/=base; 31 } 32 a[0]=t; 33 } 34 void add(int k) {if(k||a[0]) a[++a[0]]=k;} 35 void re() {reverse(a+1,a+1+a[0]);} 36 void print() 37 { 38 printf("%d",a[a[0]]); 39 for(rg int i=a[0]-1;i>0;--i) 40 printf("%0*d",power,a[i]); 41 printf(" "); 42 } 43 }p,pai; 44 45 bool operator <(const num &p,const num &q) 46 { 47 if(p.a[0]<q.a[0]) return 1; 48 if(p.a[0]>q.a[0]) return 0; 49 for(rg int i=p.a[0];i>0;--i) 50 if(p.a[i]!=q.a[i]) return p.a[i]<q.a[i]; 51 return 0; 52 } 53 54 num operator +(const num &p,const num &q) 55 { 56 num c; 57 c.a[0]=max(p.a[0],q.a[0]); 58 for(rg int i=1;i<=c.a[0];++i) 59 { 60 c.a[i]+=p.a[i]+q.a[i]; 61 c.a[i+1]+=c.a[i]/base,c.a[i]%=base; 62 } 63 if(c.a[c.a[0]+1]) ++c.a[0]; 64 return c; 65 } 66 67 int main() 68 { 69 //freopen("in.txt","r",stdin); 70 while(scanf("%lld",&n)==1&&n) 71 { 72 memset(v,0,sizeof(v)); 73 memset(t,0,sizeof(t)); 74 num ans[2005]; 75 ans[0]=num(1),cnt=0,mt=0; 76 for(rg ll i=1;i<=n;++i) rd(v[i]); 77 while(scanf("%lld",&tt)==1&&tt) t[++cnt]=tt,mt=max(mt,tt); 78 for(rg ll i=1;i<=n;++i) 79 for(rg ll j=1;j<=mt;++j) 80 { 81 if(j-v[i]>=0) ans[j]=ans[j]+ans[j-v[i]]; 82 } 83 for(ll i=1;i<=cnt;++i) ans[t[i]].print(); 84 } 85 return 0; 86 }