fps/FPS_division.hpp

View this file on GitHub
Last update: 2024-11-23 03:09:08+09:00
Include: #include "fps/FPS_division.hpp"

Depends on

fps/FPS_inv.hpp

Required by

fps/Multipoint_Evaluation.hpp

Verified with

Code

#pragma once
#include <vector>
#include <atcoder/convolution>

#include "FPS_inv.hpp"
namespace po167{
template<class T>
// f = g * res.first + res.second
// |res.first| <= |f| - |g| + 1
// |res.second| <= |g| - 1
std::pair<std::vector<T>, std::vector<T>>
FPS_division(std::vector<T> f, std::vector<T> g){
    while (!f.empty() && f.back() == 0) f.pop_back();
    assert(!g.empty() && g.back() != 0);
    if (f.size() < g.size()){
        return {{}, f};
    }
    // rev(f) / rev(g) = rev(q) (mod x ^ {|f| - |g| + 1})
    std::vector<T> r = f;
    std::reverse(f.begin(), f.end());
    std::reverse(g.begin(), g.end());
    int z = (int)f.size() - (int)g.size() + 1;
    f.resize(z);
    std::vector<T> q = atcoder::convolution(f, FPS_inv(g, z));
    q.resize(z);
    std::reverse(g.begin(), g.end());
    std::reverse(q.begin(), q.end());
    f = atcoder::convolution(q, g);
    for (int i = 0; i < (int)f.size(); i++) r[i] -= f[i];
    while (!q.empty() && q.back() == 0) q.pop_back();
    while (!r.empty() && r.back() == 0) r.pop_back();
    return {q, r};
}
}

#line 2 "fps/FPS_division.hpp"
#include <vector>
#include <atcoder/convolution>

#line 4 "fps/FPS_inv.hpp"

namespace po167{
// return 1 / f
template <class T>
std::vector<T> FPS_inv(std::vector<T> f, int len = -1){
    if (len == -1) len = f.size();
    assert(f[0] != 0);
    std::vector<T> g = {1 / f[0]};
    int s = 1;
    while(s < len){
        // g = 2g_s - f(g_s)^2 (mod x ^ (2 * s))
        // g = g - (fg - 1)g
        // (fg - 1) = 0 (mod x ^ (s))
        std::vector<T> n_g(s * 2, 0);
        std::vector<T> f_s(s * 2, 0);
        g.resize(s * 2);
        for (int i = 0; i < s * 2; i++){
            if (int(f.size()) > i) f_s[i] = f[i];
            n_g[i] = g[i];
        }
        atcoder::internal::butterfly(g);
        atcoder::internal::butterfly(f_s);
        for (int i = 0; i < s * 2; i++){
            f_s[i] *= g[i];
        }
        atcoder::internal::butterfly_inv(f_s);
        T iz = 1 / (T)(s * 2);
        for (int i = s; i < s * 2; i++){
            f_s[i] *= iz;
        }
        for (int i = 0; i < s; i++){
            f_s[i] = 0;
        }
        atcoder::internal::butterfly(f_s);
        for (int i = 0; i < s * 2; i++){
            f_s[i] *= g[i];
        }
        atcoder::internal::butterfly_inv(f_s);
        for (int i = s; i < s * 2; i++){
            n_g[i] -= f_s[i] * iz;
        }
        std::swap(n_g, g);
        s *= 2;
    }
    g.resize(len);
    return g;
}
}
#line 6 "fps/FPS_division.hpp"
namespace po167{
template<class T>
// f = g * res.first + res.second
// |res.first| <= |f| - |g| + 1
// |res.second| <= |g| - 1
std::pair<std::vector<T>, std::vector<T>>
FPS_division(std::vector<T> f, std::vector<T> g){
    while (!f.empty() && f.back() == 0) f.pop_back();
    assert(!g.empty() && g.back() != 0);
    if (f.size() < g.size()){
        return {{}, f};
    }
    // rev(f) / rev(g) = rev(q) (mod x ^ {|f| - |g| + 1})
    std::vector<T> r = f;
    std::reverse(f.begin(), f.end());
    std::reverse(g.begin(), g.end());
    int z = (int)f.size() - (int)g.size() + 1;
    f.resize(z);
    std::vector<T> q = atcoder::convolution(f, FPS_inv(g, z));
    q.resize(z);
    std::reverse(g.begin(), g.end());
    std::reverse(q.begin(), q.end());
    f = atcoder::convolution(q, g);
    for (int i = 0; i < (int)f.size(); i++) r[i] -= f[i];
    while (!q.empty() && q.back() == 0) q.pop_back();
    while (!r.empty() && r.back() == 0) r.pop_back();
    return {q, r};
}
}