// Algorithms from Theorem 2 // including the prefix sums but not the memory optimization // Using the GMPlib big integers from the CGAL library // Runtime O(n^4), Memory O(n^4) times the bigint-overhead (roughly another O(nlogn)). // Just compile and run it to get a quick demo or look at the main function for some examples: // Compilation steps with CGAL: // Run: cgal_create_cmake_script // To the file CMakeLists.txt add this line: set(CMAKE_CXX_FLAGS \${CMAKE_CXX_FLAGS} " -std=c++11") // Run: cmake . // Run: make // Execute: ./motzkin_leftright_bignum #include #include #include #include #include #include #include typedef CGAL::Gmpz bignum; using namespace std; using in = long long int; using PII = pair; using VI = vector; using VB = vector; #define sz(v) (v).size() #define forn(i,n) for(in i=0; i<(n); ++i) #define forv(i,v) forn(i,sz(v)) #define DEB(x) // Replace by "DEB(x) x" to get debug output using namespace std; bignum tob(in x) { return (bignum)(double)x; } map LFMemo; map PSLFMemo; // Prefix sums bignum LFcount(in A, in w, in l); bignum SumLFcount(in A, in w, in la, in lb) { // sum for l in [la,lb] if(la > lb) return 0; if(la < 0) return 0; if(la==lb) return LFcount(A,w,la); if(PSLFMemo.find({A,w,lb}) == PSLFMemo.end()) { PSLFMemo[{A,w,lb}] = SumLFcount(A,w,0,lb-1) + LFcount(A,w,lb); } return PSLFMemo[{A,w,lb}] - SumLFcount(A,w,0,la-1); } bignum LFcount(in A, in w, in l) { if(A==0 && w == 0 && l==0 ) { return 1; } if(A < 0 || w <= 0 || l < 0) return 0; if(LFMemo.find({A,w,l}) != LFMemo.end()) { return LFMemo[{A,w,l}]; } bignum res = 0; res += SumLFcount(A-l, w-1, l, w/2); // for(in ll = l; ll<=w/2; ll++) { // res += LFcount(A-l, w-1, ll); // } if(l>0) { res += SumLFcount(A-(2*l-1), w-2, l-1, w/2); // for(in ll = l-1; ll<=w/2; ll++) { // res += LFcount(A-(2*l-1), w-2, ll); // } } LFMemo[{A,w,l}] = res; // cout << " computed " << "LFcount(" << A << "," << w << "," << l << ") = " << res << endl; return res; } bignum LFcount(in A, in w) { bignum res = 0; for(in l = 0; l <= w; l++) { bignum x = LFcount(A,w,l); // cout << "add " << "LFcount(" << A << "," << w << "," << l << ") =... " << x << endl; res += x; } return res; } bignum LFcount(in w) { bignum res = 0; for(in A = 0; A <= w*w; A++) { res += LFcount(A,w); } return res; } // Weighted Version map WLFMemo; map PSWLFMemo; // Prefix sums bignum WLFcount(in A, in w, in l); bignum SumWLFcount(in A, in w, in la, in lb) { // sum for l in [la,lb] if(la > lb) return 0; if(la < 0) return 0; if(la==lb) return WLFcount(A,w,la); if(PSWLFMemo.find({A,w,lb}) == PSWLFMemo.end()) { PSWLFMemo[{A,w,lb}] = SumWLFcount(A,w,0,lb-1) + WLFcount(A,w,lb); } return PSWLFMemo[{A,w,lb}] - SumWLFcount(A,w,0,la-1); } bignum WLFcount(in A, in w, in l) { // cout << "A " << A << " w " << w << " l " << l << endl; if(A==0 && w == 0 && l==0 ) { // cout << "base" << endl; return 1; } if(A < 0 || w <= 0 || l < 0) return 0; if(WLFMemo.find({A,w,l}) != WLFMemo.end()) { return WLFMemo[{A,w,l}]; } bignum res = 0; res += tob(2*l+1)*SumWLFcount(A-l, w-1, l, w/2); if(l>0) { res += tob(l)*tob(l)*SumWLFcount(A-(2*l-1), w-2, l-1, w/2); } WLFMemo[{A,w,l}] = res; return res; } bignum WLFcount(in A, in w) { bignum res = 0; for(in l = 0; l <= w; l++) { bignum x = WLFcount(A,w,l); res += x; } return res; } bignum WLFcount(in w) { bignum res = 0; for(in A = 0; A <= w*w; A++) { res += WLFcount(A,w); } return res; } int main() { in A,w,h; cout << "\nMotzkin Path Counting Demo\n\n"; cout << "Motzkin Numbers from 1 to 10\n"; cout << "see: https://en.wikipedia.org/wiki/Motzkin_number\n"; for(in w = 1; w<=10; w++) { bignum res = LFcount(w); cout << "M(" << w << ") = " << res << endl; } cout << "\n\nM(n,A): Print Motzkin Path Counts by width and area using the last fall DP\n"; cout << "see: http://oeis.org/A129181\n"; for(w = 1; w<=10; w++) { for(A = 0; A <= w*w; A++) { bignum res = LFcount(A,w); // assert(res == weighted_count(A,w)); if(res>0) cout << res << "\t"; } cout << endl; } cout << "\n\nD(n,A): Print Weighted Motzkin Path Counts by width and area using the last fall DP\n"; cout << "see: https://oeis.org/A062869\n"; for(w = 1; w<=10; w++) { for(A = 0; A <= w*w; A++) { bignum res = WLFcount(A,w); // assert(res == weighted_count(A,w)); if(res>0) cout << res << "\t"; } cout << endl; } cout << "\n\nPrint Weighted Motzkin Path Counts by width for a fixed w = w!\n"; for(w = 1; w<=50; w++) { bignum res = WLFcount(w); cout << w << "! = " << res << endl; } }