**Tags:** math combinatorics misc

Rating: 4.0

First, let's say we want to count the ways as $f(x, n)$ with $x$ and $n$ as mentioned in the statement.

If we fix the largest number in our partition, we see that it always uses the most significant bit in it ($2^{n-1}$). So, we use it and we can choose any bits from the remaining $n-1$ bits.

Say we choose 2 other bits, now we have $n-3$ bits remaining, and $x-1$ parts to partition. We can count similarly for each $i$ bits, $i \in [0, n)$.

We can solve it recursively (with memoization ofcourse). The complexity is $\mathcal{O}(n^2x)$.

The recurrance is

$$f(x, n) = \sum\limits_{i=0}^{n-1}{{n-1}\choose{i}}\cdot f(x-1, n-1-i)$$

My C++ script

```cpp

#include<bits/stdc++.h>

int ncr[13][13];

int dp[5][13];

int calc(int x, int n) {

if (n == 0) return 0;

if (x == 1) return 1;

int &res = dp[x][n];

if (~res) return res;

res = 0;

for (int t = 0; t < n; ++t) {

res += ncr[n - 1][t] * calc(x - 1, n - 1 - t);

}

return res;

}

int main() {

const int X = 4, N = 12;

memset(dp, -1, sizeof dp);

for (int i = 0; i <= N; ++i) {

ncr[i][0] = 1;

for (int j = 1; j <= i; ++j) {

ncr[i][j] = ncr[i - 1][j] + ncr[i - 1][j - 1];

}

}

std::cout << "rgbCTF{" << calc(X, N) << "}" << std::endl;

}

```

Flag

```txt

rgbCTF{611501}

```

Original writeup (https://github.com/goswami-rahul/ctf/tree/master/rgbCTF2020/insert_creative_algo_chall_name).