#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) { // powers of 2 if (i==0) { return 1; } else { return 2*get(i-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 1048575+1 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; }