cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: test/src/transform/kronecker_power/agc044_c.test.cpp

Depends on

Code

#define PROBLEM "https://atcoder.jp/contests/agc044/tasks/agc044_c"

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

#include "library/transform/kronecker_power.hpp"
using suisen::kronecker_power_transform::kronecker_power_transform;

void utit_transform(int&, int &x1, int &x2) {
    std::swap(x1, x2);
}

constexpr int pow3(int b) {
    int res = 1;
    while (b --> 0) res *= 3;
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    const int sz = pow3(n), lsz = pow3(n - n / 2), usz = pow3(n / 2);

    std::string s;
    std::cin >> s;
    const int k = s.size();

    std::vector<bool> cnt_s(k + 1, false);
    std::vector<int> ql(lsz);
    std::iota(ql.begin(), ql.end(), 0);
    std::vector<std::vector<int>> carry(lsz);
    for (int i = 0; i < k; ++i) {
        cnt_s[i + 1] = cnt_s[i] ^ (s[i] == 'S');
        if (s[i] == 'S') {
            kronecker_power_transform<int, 3, utit_transform>(ql);
        } else {
            std::rotate(ql.begin(), ql.end() - 1, ql.end());
            carry[ql[0]].push_back(i);
        }
    }

    std::vector<int> p(sz);

    for (int lower = 0; lower < lsz; ++lower) {
        std::vector<int> qu(usz);
        std::iota(qu.begin(), qu.end(), 0);
        int pj = 0;
        for (int j : carry[ql[lower]]) {
            if (cnt_s[j] ^ cnt_s[pj]) kronecker_power_transform<int, 3, utit_transform>(qu);
            pj = j;
            std::rotate(qu.begin(), qu.end() - 1, qu.end());
        }
        if (cnt_s[pj] ^ cnt_s[k]) kronecker_power_transform<int, 3, utit_transform>(qu);
        for (int upper = 0; upper < usz; ++upper) {
            int pos = upper * lsz + lower;
            int idx = qu[upper] * lsz + ql[lower];
            p[idx] = pos;
        }
    }
    
    for (int i = 0; i < sz; ++i) {
        std::cout << p[i] << ' ';
    }
    std::cout << std::endl;
    return 0;
}
#line 1 "test/src/transform/kronecker_power/agc044_c.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/agc044/tasks/agc044_c"

#include <algorithm>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

#line 1 "library/transform/kronecker_power.hpp"



#include <cassert>
#include <utility>
#line 7 "library/transform/kronecker_power.hpp"

#line 1 "library/util/default_operator.hpp"



namespace suisen {
    namespace default_operator {
        template <typename T>
        auto zero() -> decltype(T { 0 }) { return T { 0 }; }
        template <typename T>
        auto one()  -> decltype(T { 1 }) { return T { 1 }; }
        template <typename T>
        auto add(const T &x, const T &y) -> decltype(x + y) { return x + y; }
        template <typename T>
        auto sub(const T &x, const T &y) -> decltype(x - y) { return x - y; }
        template <typename T>
        auto mul(const T &x, const T &y) -> decltype(x * y) { return x * y; }
        template <typename T>
        auto div(const T &x, const T &y) -> decltype(x / y) { return x / y; }
        template <typename T>
        auto mod(const T &x, const T &y) -> decltype(x % y) { return x % y; }
        template <typename T>
        auto neg(const T &x) -> decltype(-x) { return -x; }
        template <typename T>
        auto inv(const T &x) -> decltype(one<T>() / x)  { return one<T>() / x; }
    } // default_operator
    namespace default_operator_noref {
        template <typename T>
        auto zero() -> decltype(T { 0 }) { return T { 0 }; }
        template <typename T>
        auto one()  -> decltype(T { 1 }) { return T { 1 }; }
        template <typename T>
        auto add(T x, T y) -> decltype(x + y) { return x + y; }
        template <typename T>
        auto sub(T x, T y) -> decltype(x - y) { return x - y; }
        template <typename T>
        auto mul(T x, T y) -> decltype(x * y) { return x * y; }
        template <typename T>
        auto div(T x, T y) -> decltype(x / y) { return x / y; }
        template <typename T>
        auto mod(T x, T y) -> decltype(x % y) { return x % y; }
        template <typename T>
        auto neg(T x) -> decltype(-x) { return -x; }
        template <typename T>
        auto inv(T x) -> decltype(one<T>() / x)  { return one<T>() / x; }
    } // default_operator
} // namespace suisen


#line 9 "library/transform/kronecker_power.hpp"

namespace suisen {
    namespace kronecker_power_transform {
        namespace internal {
            template <typename UnitTransform, typename ReferenceGetter, std::size_t... Seq>
            void unit_transform(UnitTransform transform, ReferenceGetter ref_getter, std::index_sequence<Seq...>) {
                transform(ref_getter(Seq)...);
            }
        }

        template <typename T, std::size_t D, auto unit_transform>
        void kronecker_power_transform(std::vector<T> &x) {
            const std::size_t n = x.size();
            for (std::size_t block = 1; block < n; block *= D) {
                for (std::size_t l = 0; l < n; l += D * block) {
                    for (std::size_t offset = l; offset < l + block; ++offset) {
                        const auto ref_getter = [&](std::size_t i) -> T& { return x[offset + i * block]; };
                        internal::unit_transform(unit_transform, ref_getter, std::make_index_sequence<D>());
                    }
                }
            }
        }

        template <typename T, typename UnitTransform>
        void kronecker_power_transform(std::vector<T> &x, const std::size_t D, UnitTransform unit_transform) {
            const std::size_t n = x.size();
            std::vector<T> work(D);
            for (std::size_t block = 1; block < n; block *= D) {
                for (std::size_t l = 0; l < n; l += D * block) {
                    for (std::size_t offset = l; offset < l + block; ++offset) {
                        for (std::size_t i = 0; i < D; ++i) work[i] = x[offset + i * block];
                        unit_transform(work);
                        for (std::size_t i = 0; i < D; ++i) x[offset + i * block] = work[i];
                    }
                }
            }
        }

        template <typename T, auto e = default_operator::zero<T>, auto add = default_operator::add<T>, auto mul = default_operator::mul<T>>
        auto kronecker_power_transform(std::vector<T> &x, const std::vector<std::vector<T>> &A) -> decltype(e(), add(std::declval<T>(), std::declval<T>()), mul(std::declval<T>(), std::declval<T>()), void()) {
            const std::size_t D = A.size();
            assert(D == A[0].size());
            auto unit_transform = [&](std::vector<T> &x) {
                std::vector<T> y(D, e());
                for (std::size_t i = 0; i < D; ++i) for (std::size_t j = 0; j < D; ++j) {
                    y[i] = add(y[i], mul(A[i][j], x[j]));
                }
                x.swap(y);
            };
            kronecker_power_transform<T>(x, D, unit_transform);
        }
    }
} // namespace suisen



#line 10 "test/src/transform/kronecker_power/agc044_c.test.cpp"
using suisen::kronecker_power_transform::kronecker_power_transform;

void utit_transform(int&, int &x1, int &x2) {
    std::swap(x1, x2);
}

constexpr int pow3(int b) {
    int res = 1;
    while (b --> 0) res *= 3;
    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    const int sz = pow3(n), lsz = pow3(n - n / 2), usz = pow3(n / 2);

    std::string s;
    std::cin >> s;
    const int k = s.size();

    std::vector<bool> cnt_s(k + 1, false);
    std::vector<int> ql(lsz);
    std::iota(ql.begin(), ql.end(), 0);
    std::vector<std::vector<int>> carry(lsz);
    for (int i = 0; i < k; ++i) {
        cnt_s[i + 1] = cnt_s[i] ^ (s[i] == 'S');
        if (s[i] == 'S') {
            kronecker_power_transform<int, 3, utit_transform>(ql);
        } else {
            std::rotate(ql.begin(), ql.end() - 1, ql.end());
            carry[ql[0]].push_back(i);
        }
    }

    std::vector<int> p(sz);

    for (int lower = 0; lower < lsz; ++lower) {
        std::vector<int> qu(usz);
        std::iota(qu.begin(), qu.end(), 0);
        int pj = 0;
        for (int j : carry[ql[lower]]) {
            if (cnt_s[j] ^ cnt_s[pj]) kronecker_power_transform<int, 3, utit_transform>(qu);
            pj = j;
            std::rotate(qu.begin(), qu.end() - 1, qu.end());
        }
        if (cnt_s[pj] ^ cnt_s[k]) kronecker_power_transform<int, 3, utit_transform>(qu);
        for (int upper = 0; upper < usz; ++upper) {
            int pos = upper * lsz + lower;
            int idx = qu[upper] * lsz + ql[lower];
            p[idx] = pos;
        }
    }
    
    for (int i = 0; i < sz; ++i) {
        std::cout << p[i] << ' ';
    }
    std::cout << std::endl;
    return 0;
}
Back to top page