#include <iostream> #include <string.h> #include <vector> using namespace std; #define MAX (1LL<<32) long long get(long long i); long long compute(long long i) { // Catalan numbers switch (i) { case 0: return 1LL; case 1: return 1LL; case 2: return 2LL; case 3: return 5LL; case 4: return 14LL; case 5: return 42LL; case 6: return 132LL; case 7: return 429LL; case 8: return 1430LL; case 9: return 4862LL; case 10: return 16796LL; case 11: return 58786LL; case 12: return 208012LL; case 13: return 742900LL; case 14: return 2674440LL; case 15: return 9694845LL; case 16: return 35357670LL; case 17: return 129644790LL; case 18: return 477638700LL; case 19: return 1767263190LL; case 20: return 6564120420LL; case 21: return 24466267020LL; case 22: return 91482563640LL; case 23: return 343059613650LL; case 24: return 1289904147324LL; case 25: return 4861946401452LL; case 26: return 18367353072152LL; case 27: return 69533550916004LL; case 28: return 263747951750360LL; case 29: return 1002242216651368LL; case 30: return 3814986502092304LL; default: exit(1); } } vector<long long> f; long long get(long long i) { while (i>=f.size()) { f.push_back(compute(f.size())); } return f[i]; } #define NB 16796 long long nb[NB]; int main() { bool *sums = new bool[MAX]; memset(sums, 0, MAX*sizeof(*sums)); sums[0] = true; memset(nb, 0, sizeof(nb)); nb[0] = 1; long long total = 0; long long limit = 0; long long n = 0; for (long long v=1; v<NB; v++) { while (get(limit) < v+total) { limit++; } bool keep = true; long long d; for (long long t=limit; (d=get(t)-v)>=0; t--) { if (d<MAX && sums[d]) { keep = false; break; } } if (keep) { for (long long o=total; o>=0; o--) { if (sums[o]) { if (o+v>=MAX) { delete[] sums; return 1; } sums[o+v] = true; if (o+v<NB) { nb[o+v]+=nb[o]; } } } total += v; } } for (long long n=0; n<NB; n++) { cout << n << ' ' << nb[n] << endl; } delete[] sums; return 0; }