Pascal (Linear Complexity) with Prime Modulo (Extended GCD)

LinearPascalWithPrimeModulo.cpp

#include <bits/stdc++.h>
#define optimize_io ios_base::sync_with_stdio(0);cin.tie(0);
#define dd(x) cout << #x << ": " << x << endl;
#define MAXN ((int)(1e6+5))
#define MOD ((int)(1e9+7))
#define NOT_DEFINED -1
using namespace std;
typedef unsigned long long int ulli;
typedef long long int lli;

lli N;
lli DP[MAXN];

lli gcdExtended(lli a, lli b, lli &x, lli &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}

	lli x2, y2, q = a / b, r = a % b;
	lli g = gcdExtended(b, r, x2, y2);

	x = y2;
	y = x2 - (q * y2);
	
	return g;
}

inline lli mod(lli n) {
	return ((n % MOD) + MOD) % MOD;
}

inline lli modMult(lli a, lli b) {
	return ((a % MOD) * (b % MOD)) % MOD;
}

lli modInverse(lli a, lli m, bool &defined) {
	lli x, y;
	lli g = gcdExtended(a, m, x, y);

	if (g != 1) {
		defined = false;
	} else {
		defined = true;
	}

	/* cout << "(" << a << " * " << x << ") + (" << m << " * " << y << ") = " << g << endl; */
	return mod(x);
}

lli modDiv(lli a, lli b) {
	bool defined;
	a = a % MOD;
	lli inv = modInverse(b, MOD, defined);

	if (!defined) {
		cout << "> DIVISION NOT DEFINED!!!" << endl;
	} else {
		return (a * inv) % MOD;
	}
}

void pascal() {
	DP[0] = 1;
	cout << DP[0] << endl;
	for (int k = 1; k <= N; ++k) {
		DP[k] = modMult(DP[k - 1], (N - k + 1));
		DP[k] = modDiv(DP[k], k);
		cout << DP[k] << endl;
	}
}

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