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;
}