Linalg IHW 2 task 1

main.cpp

#include <iostream>
#include "permutation.h"
#include "polynomial.h"

using namespace std;

int main() {

    Permutation P1(vector<size_t>{1, 4, 8, 5, 2, 3, 6, 7});
    Permutation P2(vector<size_t>{7, 3, 4, 8, 2, 5, 1, 6});
    Permutation P3(vector<size_t>{3, 1, 6, 4, 7, 8, 2, 5});

    Permutation ans(P1);
    do {
        if (bin_power(bin_power(P1, 17) * P2.inversed(), 142) * ans == P3)
            break;
    } while (ans.next());
    cout << "Answer:" << endl;
    cout << ans << endl << endl;
    cout << "Check:" << endl;
    cout << bin_power(bin_power(P1, 17) * P2.inversed(), 142) * ans << endl;
    cout << "must be" << endl;
    cout << P3;

}

permutation.h

#pragma once

#include <iostream>
#include <vector>

class Permutation {
    std::vector<size_t> perm;

public:

    Permutation() {}

    Permutation(size_t n) {
        perm.reserve(n);
        for (size_t i = 0; i < n; ++i)
            perm.push_back(i);
    }

    Permutation(std::vector<size_t> _perm): perm(_perm) {
        if (std::find(perm.begin(), perm.end(), 0) == perm.end())
            for (size_t i = 0; i < perm.size(); ++i)
                --perm[i];
    }

    bool next() {
        if (perm.size() < 2)
            return false;
        size_t cur = perm.size() - 1;
        while (perm[cur - 1] > perm[cur]) {
            --cur;
            if (cur == 0)
                return false;
        }

        size_t nxt = perm.size() - 1;
        while (nxt > cur && perm[nxt] < perm[cur - 1])
            --nxt;

        std::swap(perm[nxt], perm[cur - 1]);

        std::reverse(perm.begin() + cur, perm.end());
        return true;
    }

    size_t size() const {
        return perm.size();
    }

    size_t operator[](size_t p) const {
        return perm[p];
    }

    size_t& operator[](size_t p) {
        return perm[p];
    }

    friend std::ostream& operator<<(std::ostream &os, const Permutation& P) {
        for (size_t i = 0; i < P.size(); ++i)
            os << i + 1 << '\t';
        os << std::endl;
        for (size_t i = 0; i < P.size(); ++i)
            os << P.perm[i] + 1 << '\t';
        return os;
    }

    Permutation& operator*=(const Permutation& other) {
        std::vector<size_t> tmp(size());
        for (size_t i = 0; i < size(); ++i) {
            tmp[i] = perm[other[i]];
        }
        perm = std::move(tmp);
        return *this;
    }

    friend Permutation operator*(const Permutation& P1, const Permutation& P2) {
        Permutation tmp(P1);
        tmp *= P2;
        return tmp;
    }

    Permutation inversed() const {
        Permutation tmp(size());
        for (size_t i = 0; i < size(); ++i)
            tmp[perm[i]] = i;
        return tmp;
    }

    bool operator==(const Permutation& P) const {
        return perm == P.perm;
    }
};

polynomial.h

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

template <typename T>
T bin_power(const T& a, int p) {
    if (p == 0)
        return T(1);
    if (p == 1)
        return a;
    T x = bin_power(a, p / 2);
    x = x * x;
    if (p % 2 == 1)
        x = x * a;
    return x;
}

template<typename T = int>
class Polynomial {
public:
    std::vector<std::pair<int, T>> coeffs;

    Polynomial() {
        coeffs.emplace_back(0, T());
    }

    explicit Polynomial(const std::vector<T>& in_coeffs) {
        int cnt = 0;
        for (const T& el : in_coeffs) {
            if (el != T(0))
                coeffs.emplace_back(cnt, el);
            cnt++;
        }
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
    }

    explicit Polynomial(const std::pair<int, T>& monom) {
        coeffs.push_back(monom);
    }

    Polynomial(const T& single) {
        coeffs.emplace_back(0, single);
    }

    template<typename It>
    Polynomial(It first, It last) {
        int cnt = 0;
        while (first != last) {
            if (*first != T(0))
                coeffs.emplace_back(cnt, *first);
            cnt++;
            ++first;
        }
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
    }

    Polynomial& operator+=(const Polynomial<T>& other) {
        auto first1 = other.coeffs.begin();
        auto first2 = coeffs.begin();
        std::vector<std::pair<int, T>> new_coeffs;
        while (first1 != other.coeffs.end() && first2 != coeffs.end()) {
            if (first1->first < first2->first) {
                if (first1->second != T(0))
                    new_coeffs.push_back(*first1);
                first1++;
            } else if (first1->first == first2->first) {
                if (first1->second + first2->second != T(0))
                    new_coeffs.emplace_back(first1->first, first1->second + first2->second);
                first1++;
                first2++;
            } else {
                if (first2->second != T(0))
                    new_coeffs.push_back(*first2);
                first2++;
            }
        }
        while (first1 != other.coeffs.end()) {
            if (first1->second != T(0))
                new_coeffs.push_back(*first1);
            first1++;
        }
        while (first2 != coeffs.end()) {
            if (first2->second != T(0))
                new_coeffs.push_back(*first2);
            first2++;
        }
        coeffs = std::move(new_coeffs);
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
        return *this;
    }

    friend Polynomial operator+(const Polynomial<T>& P1, const Polynomial<T>& P2) {
        Polynomial tmp(P1);
        tmp += P2;
        return tmp;
    }

    Polynomial& operator-=(const Polynomial<T>& other) {
        auto first1 = other.coeffs.begin();
        auto first2 = coeffs.begin();
        std::vector<std::pair<int, T>> new_coeffs;
        while (first1 != other.coeffs.end() && first2 != coeffs.end()) {
            if (first1->first < first2->first) {
                if (first1->second != T(0))
                    new_coeffs.emplace_back(first1->first, -first1->second);
                first1++;
            } else if (first1->first == first2->first) {
                if (first1->second - first2->second != T(0))
                    new_coeffs.emplace_back(first1->first, first2->second - first1->second);
                first1++;
                first2++;
            } else {
                if (first2->second != T(0))
                    new_coeffs.push_back(*first2);
                first2++;
            }
        }
        while (first1 != other.coeffs.end()) {
            if (first1->second != T(0))
                new_coeffs.emplace_back(first1->first, -first1->second);
            first1++;
        }
        while (first2 != coeffs.end()) {
            if (first2->second != 0)
                new_coeffs.push_back(*first2);
            first2++;
        }
        coeffs = std::move(new_coeffs);
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
        return *this;
    }

    friend Polynomial operator-(const Polynomial<T>& P1, const Polynomial<T>& P2) {
        Polynomial tmp(P1);
        tmp -= P2;
        return tmp;
    }

    Polynomial& operator*=(const Polynomial<T>& other) {
        std::map<int, T> tmp;
        for (const auto& first : coeffs) {
            for (const auto& second : other.coeffs) {
                if (first.second != T(0) && second.second != T(0))
                    tmp[first.first + second.first] += first.second * second.second;
            }
        }
        std::vector<std::pair<int, T>> new_coeffs;
        for (const auto& it : tmp) {
            if (it.second != T(0)) {
                new_coeffs.push_back(it);
            }
        }
        coeffs = std::move(new_coeffs);
        if (coeffs.empty())
            coeffs.emplace_back(0, T());
        return *this;
    }

    friend Polynomial operator*(const Polynomial<T>& P1, const Polynomial<T>& P2) {
        Polynomial tmp(P1);
        tmp *= P2;
        return tmp;
    }

    T operator()(const T& x) const {
        T ans = T();
        for (const auto& it : coeffs) {
            ans += bin_power(x, it.first) * it.second;
        }
        return ans;
    }

    typename std::vector<std::pair<int, T>>::const_iterator begin() const {
        return coeffs.cbegin();
    }

    typename std::vector<std::pair<int, T>>::const_iterator end() const {
        return coeffs.cend();
    }

    friend std::ostream& operator<<(std::ostream &out, const Polynomial<T>& P) {
        bool was_output = false;
        for (auto it = P.coeffs.rbegin(); it != P.coeffs.rend(); ++it) {
            if (it->second == T(0))
                continue;
            if (it->second < T(0))
                out << '-';
            else if (was_output)
                out << '+';
            if (abs(it->second) != T(1) || it->first == 0)
                out << std::abs(it->second);
            if ((abs(it->second) != T(1) || it->first == 0) && it->first != 0)
                out << '*';
            if (it->first != 0)
                out << 'x';
            if (it->first > 1)
                out << '^' << it->first;
            was_output = true;
        }
        if (!was_output)
            out << T(0);
        return out;
    }

    T operator[](int p) const {
        for (const auto& it : coeffs) {
            if (it.first == p)
                return it.second;
        }
        return T(0);
    }

    int Degree() const {
        int ans = -1;
        for (const auto& it : coeffs) {
            if (it.second != T(0))
                ans = it.first;
        }
        return ans;
    }

    Polynomial& operator/=(const Polynomial &P) {
        std::vector<std::pair<int, T>> new_coeffs;
        while (!coeffs.empty() && coeffs.rbegin()->first >= P.coeffs.rbegin()->first) {
            T coef = coeffs.rbegin()->second / P.coeffs.rbegin()->second;
            int pow = coeffs.rbegin()->first - P.coeffs.rbegin()->first;
            if (coef == T(0))
                break;
            *this -= P * Polynomial(std::make_pair(pow, coef));
            if (coef != T(0))
                new_coeffs.emplace_back(pow, coef);
        }
        reverse(new_coeffs.begin(), new_coeffs.end());
        coeffs = std::move(new_coeffs);
        return *this;
    }

    friend Polynomial operator/(const Polynomial& P1, const Polynomial& P2) {
        Polynomial tmp(P1);
        tmp /= P2;
        return tmp;
    }

    Polynomial& operator%=(const Polynomial &P) {
        while (!coeffs.empty() && coeffs.rbegin()->first >= P.coeffs.rbegin()->first) {
            T coef = coeffs.rbegin()->second / P.coeffs.rbegin()->second;
            int pow = coeffs.rbegin()->first - P.coeffs.rbegin()->first;
            if (coef == T(0))
                break;
            *this -= P * Polynomial(std::make_pair(pow, coef));
        }
        while (!coeffs.empty() && coeffs.back().second == T(0))
            coeffs.pop_back();
        return *this;
    }

    friend Polynomial operator%(const Polynomial& P1, const Polynomial& P2) {
        Polynomial tmp(P1);
        tmp %= P2;
        return tmp;
    }

    friend Polynomial operator&(const Polynomial &P1, const Polynomial &P2) {
        Polynomial result;
        for (const auto& first : P1) {
            result += bin_power(P2, first.first) * first.second;
        }
        return result;
    }

    friend Polynomial operator,(const Polynomial& P1, const Polynomial& P2) {
        if (P1.Degree() == -1)
            return P2;
        auto tmp = (P2 % P1, P1);
        if (tmp.coeffs.back().second != T(0))
            tmp /= tmp.coeffs.back().second;
        return tmp;
    }
};

template<typename T1, typename T2>
bool operator==(const Polynomial<T1>& P1, const Polynomial<T2>& P2) {
    return P1.coeffs == P2.coeffs;
}

template<typename T1, typename T2>
bool operator==(const T1& single, const Polynomial<T2>& P2) {
    return Polynomial<T1>(single).coeffs == P2.coeffs;
}

template<typename T1, typename T2>
bool operator==(const Polynomial<T2>& P2, const T1& single) {
    return Polynomial<T1>(single).coeffs == P2.coeffs;
}

template<typename T1, typename T2>
bool operator!=(const Polynomial<T1>& P1, const Polynomial<T2>& P2) {
    return P1.coeffs != P2.coeffs;
}

template<typename T1, typename T2>
bool operator!=(const T1& single, const Polynomial<T2>& P2) {
    return Polynomial<T1>(single).coeffs != P2.coeffs;
}

template<typename T1, typename T2>
bool operator!=(const Polynomial<T2>& P2, const T1& single) {
    return Polynomial<T1>(single).coeffs != P2.coeffs;
}