526. Beautiful Arrangement

[!info] https://leetcode.com/problems/beautiful-arrangement/description/

#include <iostream>
#include <numeric>
#include <print>
#include <ranges>
#include <vector>

int beautifulArrangements(int n) {
    auto dp = std::vector<std::optional<int>>(1 << n, std::nullopt);
    auto countArrangements = [&](this auto&& self, int mask, int curNum) {
        if (dp[mask]) {
            return;
        }
        if (curNum == 0) {
            dp[mask] = 1;
            return;
        }
        dp[mask] = 0;
        for (int i: std::views::iota(0, n)) {
            if (mask & (1 << i)) {
                continue;
            }
            if (curNum % (i + 1) == 0 || (i + 1) % curNum == 0) {
                self(mask | (1 << i), curNum - 1);
                *dp[mask] += *dp[mask | (1 << i)];
            }
        }
    };

    countArrangements(0, n);
    return *dp[0];
}

namespace BalasubramanianBaxFranklinGlynn {
    // Balasubramanian–Bax–Franklin–Glynn formula
    // ToDo

    int beautifulArrangements(int n) {
        auto aElem = [](int i, int j) -> int {
            ++i; ++j;
            return i % j == 0 || j % i == 0;
        };

        auto countArrangements = [
            deltaProd = 1,
            deltaASum = std::vector<int64_t>(n),
            n = n,
            aElem = aElem
        ](
            this auto&& self,
            int k,
            int delta
        ) -> int64_t {
            if (k == n) {
                return std::accumulate(
                    deltaASum.cbegin(), deltaASum.cend(),
                    deltaProd, std::multiplies<>()
                );
            }

            deltaProd *= delta;
            for (int i: std::views::iota(0, n)) {
                deltaASum[i] += delta * aElem(k, i);
            }

            auto result = self(k + 1, 1) + self(k + 1, -1);

            deltaProd *= delta;
            for (int i: std::views::iota(0, n)) {
                deltaASum[i] -= delta * aElem(k, i);
            }

            return result;
        };

        return countArrangements(0, 1) / (int64_t(1) << (n));
    }
}

int main() {
    std::println("{}", BalasubramanianBaxFranklinGlynn::beautifulArrangements(10));
}