LEM6 - BIRTHDAY

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>

using namespace std;

#define coso 100000000
#define maxcs 30

struct BigNum {
	int a[maxcs];
	int cs;
};

int n, m, a[1010];
BigNum F[1010][550];

void cong(BigNum &a, BigNum &b) {
	int cc = a.cs >? b.cs, i, n;
	for(i=n=0;i<cc;++i) a.a[i] += b.a[i] + n, n = a.a[i] / coso, a.a[i] %= coso;
	if(n!=0) a.a[cc++] = n;
	a.cs = cc;
}

int main() {
	cin >> n >> m;
	for(int i=0;i<m;++i) cin >> a[i];
	for(int i=0;i<=n;++i) F[i][0].a[0] = 1, F[i][0].cs = 1;
	for(int i=0;i<=n;++i) for(int j=0;j<m;++j) {
		int ni = i + a[j] + (j==0?0:1);
		if(ni<=n) cong(F[ni][j+1], F[i][j]);
		if(i<n) cong( F[i+1][j], F[i][j]);
	}
	int *res = F[n][m].a, ok = true;
	for(int i=maxcs-1;i>=0;--i) if(res[i]>0) {
		printf("%d", res[i]);
		for(int j=i-1;j>=0;--j) printf("%08d",res[j]);
		ok = false;
		break;
	}
	if(ok) puts("0");
	return 0;
}

Download