#include #include #define MAX 40 // <= 63 long long nb[MAX+1]; // check if starts with square of len w/2 bool startsWithSquare(int w, long long val) { long long mask = (1LL << (w/2)) - 1; return (val & mask) == ((val >> (w/2)) & mask); } // check if starts with square of len 1 to w/2 bool endsWithSquare(int w, long long val) { long long mask = 1ll; long long rem = val; for (int s=1; s<=w/2; s++) { rem >>= 1; if ((val & mask) == (rem & mask)) { return true; } mask = (mask<<1) + 1ll; } return false; } void explore(int w, long long val) { if (w%2 || !startsWithSquare(w, val)) { if (!endsWithSquare(w, val)) { nb[w]++; } if (w