LEM6 - BIRTHDAY

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

const int BASE = 10000, MAXLEN = 100;
struct BigInteger {
	int d[MAXLEN], n;

	BigInteger (int x = 0) {
		memset(d, 0, sizeof d); n = 0;
		for(; x != 0; x /= BASE) d[n++] = x % BASE;
	}

	void operator = (int x) {
		memset(d, 0, sizeof d); n = 0;
		for(; x != 0; x /= BASE) d[n++] = x % BASE;
	}

	BigInteger operator + (const BigInteger &x) const {
		BigInteger res; res.n = max(n, x.n);
		int rem = 0;
		for(int i = 0; i < res.n; ++i) {
			int t = x.d[i] + d[i] + rem;
			res.d[i] = t % BASE;
			rem = t / BASE;
		}
		if(rem) res.d[res.n++] = rem;
		return res;
	}
};

ostream& operator << (ostream &out, const BigInteger &x) {
	if(x.n == 0) out << 0;
	else {
		out << x.d[x.n-1];
		for(int i = x.n-2; i >= 0; --i)
			out << setfill('0') << setw(4) << x.d[i];
	}
	return out;
}

const int N = 1000;
BigInteger f[N+1][2];
int n, m, a[N];

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i = 0; i < m; ++i) cin >> a[i];
	for(int i = 1; i < m; ++i) ++a[i];
	for(int i = 0; i <= n; ++i) f[i][0] = 1;
	for(int j = 1; j <= m; ++j) {
		f[0][j % 2] = 0;
		for(int i = 1; i <= n; ++i) {
			if(i >= a[j-1]) f[i][j % 2] = f[i-1][j % 2] + f[i-a[j-1]][(j-1) % 2];
			else f[i][j % 2] = f[i-1][j % 2];
		}
	}
	cout << f[n][m % 2] << '\n';
	return 0;
}

Download