Pascal's Triangle with Bitmasks (DP Solution)

DP-Pascal-Triangle-with-Bitmasks.cpp

#include <bits/stdc++.h>
#define dd(x) cout << #x << ": " << x << endl;
#define MAXN 1000003
#define MOD 1000000007
using namespace std;
typedef long long int lli;

int N;
lli dp[2][MAXN];

void pascal() {
	int i, j, idx = 1;

	dp[0][1] = 1;

	for (i = 1; i <= N; ++i) {
		for (j = 1; j <= (i + 1); ++j) {
			dp[idx][j] = dp[idx ^ 1][j] + dp[idx ^ 1][j - 1];
			dp[idx][j] %= MOD;
		}
		idx ^= 1;
	}

	idx ^= 1;

	for (i = 1; i <= (N + 1); ++i) {
		if (i > 1) {
			cout << ' ';
		}

		cout << dp[idx][i];
	}

	cout << '\n';
}

int main() {
	cin >> N;
	pascal();
	return 0;
}