一本通OJ 1273

题目分析：

• 边界$f[0]=1$f[0]=1
• 转移方程$f[j]+=f[j-a[i]]$f[j]+=f[j−a[i]]
• 注意$f[]$f[]要开$long long$longlong

Code :

#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
#define maxm 100000

int n,m,a[maxn];
long long f[maxm];

inline void init_() {
	freopen("a.txt","r",stdin);
}

inline int read_() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x*f;
}

inline void clean_() {
	memset(f,0,sizeof(f));
}

void readda_() {
	clean_();
	n=read_();m=read_();
	for(int i=1;i<=n;++i) {
		a[i]=read_();
	}	
	f[0]=1;
	for(int i=1;i<=n;++i) {
		for(int j=a[i];j<=m;++j) {
			f[j]+=f[j-a[i]];
		}
	}
	printf("%lld",f[m]);
}

int main() {
	init_();
	readda_();
	return 0;
}