// Algorithms from Theorem 2 // including the prefix sums but not the memory optimization // no big integers used, everything will overflow at 2^63 // Runtime O(n^4), Memory O(n^4) // Just compile and run it to get a quick demo or look at the main function for some examples. // g++ motzkin.cpp -o m -std=c++11 -O2; ./m #include #include #include #include #include using namespace std; using in = long long int; using PII = pair; using VI = 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; map LFMemo; map PSLFMemo; // Prefix sums in LFcount(in A, in w, in l); in 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); } in 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}]; } in 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; } in LFcount(in A, in w) { in res = 0; for(in l = 0; l < w; l++) { in x = LFcount(A,w,l); // cout << "add " << "LFcount(" << A << "," << w << "," << l << ") =... " << x << endl; res += x; } return res; } in LFcount(in w) { in res = 0; for(in A = 0; A < w*w; A++) { res += LFcount(A,w); } return res; } // Weighted Version map WLFMemo; map PSWLFMemo; // Prefix sums in WLFcount(in A, in w, in l); in 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); } in WLFcount(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(WLFMemo.find({A,w,l}) != WLFMemo.end()) { return WLFMemo[{A,w,l}]; } in res = 0; res += (2*l+1)*SumWLFcount(A-l, w-1, l, w/2); if(l>0) { res += l*l*SumWLFcount(A-(2*l-1), w-2, l-1, w/2); } WLFMemo[{A,w,l}] = res; return res; } in WLFcount(in A, in w) { in res = 0; for(in l = 0; l < w; l++) { in x = WLFcount(A,w,l); res += x; } return res; } in WLFcount(in w) { in 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++) { in 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++) { in 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"; for(w = 1; w<=10; w++) { for(A = 0; A <= w*w; A++) { in 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<10; w++) { in res = WLFcount(w); cout << w << "! = " << res << endl; } }