fps/mod_pow.hpp

• View this file on GitHub
• Last update: 2025-01-05 07:17:08+09:00
• Include: #include "fps/mod_pow.hpp"

Required by

• fps/poly_find_root.hpp

Verified with

• verify/yosupo_fps/poly_root_finding.test.cpp

Code

#ifndef KK2_FPS_MOD_POW_HPP
#define KK2_FPS_MOD_POW_HPP 1

#include <cassert>

namespace kk2 {

// return f ^ k mod g
template <class FPS, class mint = typename FPS::value_type, class T>
FPS mod_pow(T k, const FPS &f, const FPS &g) {
    // assert(!is_signed_v<T> || k >= 0);
    assert(!g.empty());

    auto inv = g.rev().inv();
    auto quo = [&](const FPS &poly) {
        if (poly.size() < g.size()) return FPS{};
        int n = poly.size() - g.size() + 1;
        return (poly.rev().pre(n) * inv.pre(n)).pre(n).rev();
    };
    FPS res{1}, b(f);
    while (k) {
        if (k & 1) {
            res *= b;
            res -= quo(res) * g;
            res.shrink();
        }
        b *= b;
        b -= quo(b) * g;
        b.shrink();
        k >>= 1;
    }
    return res;
}

} // namespace kk2

#endif // KK2_FPS_MOD_POW_HPP

#line 1 "fps/mod_pow.hpp"



#include <cassert>

namespace kk2 {

// return f ^ k mod g
template <class FPS, class mint = typename FPS::value_type, class T>
FPS mod_pow(T k, const FPS &f, const FPS &g) {
    // assert(!is_signed_v<T> || k >= 0);
    assert(!g.empty());

    auto inv = g.rev().inv();
    auto quo = [&](const FPS &poly) {
        if (poly.size() < g.size()) return FPS{};
        int n = poly.size() - g.size() + 1;
        return (poly.rev().pre(n) * inv.pre(n)).pre(n).rev();
    };
    FPS res{1}, b(f);
    while (k) {
        if (k & 1) {
            res *= b;
            res -= quo(res) * g;
            res.shrink();
        }
        b *= b;
        b -= quo(b) * g;
        b.shrink();
        k >>= 1;
    }
    return res;
}

} // namespace kk2

Back to top page