ボスタン森法
(fps/FPS_Boston_Mori.hpp)

View this file on GitHub
Last update: 2024-06-19 15:49:30+09:00
Include: #include "fps/FPS_Boston_Mori.hpp"

ボスタン森法

T Boston_Mori(long long k, std::vector<T> P, std::vector<T> Q)

$x^{k}$ を返す関数

$N = \max(

)$ として、 $O(N\log(N)\log(k))$

$Q(x)$ の DFT から $Q(-x)$ の DFT が簡単に求まることや、偶奇の取り出し、$0$ 詰めなどの高速化を行なっている。

線形漸化式

T Kth_Linear(long long k, std::vector<T> a, std::vector<T> c)

= d,

= d + 1$ を満たす数列 $a, c$ を用いて、以下を満たす正整数列 $b$ の $k$ 項目を求める。

$0\leq i< d\implies b_{i} = a_{i}$
$k\leq i\implies 0 = \sum_{j = 0}^{d}b_{i - j}c_{j}$

計算量は $O(d\log(d)\log(k))$

Depends on

Verified with

test/fps/linear_kth.test.cpp

Code

#pragma once
#include <vector>
#include <atcoder/convolution>
#include <cassert>
#include "FPS_extend.hpp"
#include "FPS_pick_even_odd.hpp"

namespace po167{
// return [x^k] P(x) / Q(x)
template<class T>
T Boston_Mori(long long k, std::vector<T> P, std::vector<T> Q){
    assert(!Q.empty() && Q[0] != 0);
    int z = 1;
    while (z < (int)std::max(P.size(), Q.size())) z *= 2;
    P.resize(z * 2, 0);
    Q.resize(z * 2, 0);
    atcoder::internal::butterfly(P);
    atcoder::internal::butterfly(Q);

    // fast
    while (k){
        // Q(-x)
        std::vector<T> Q_n(z * 2);
        for (int i = 0; i < z; i++){
            Q_n[i * 2] = Q[i * 2 + 1];
            Q_n[i * 2 + 1] = Q[i * 2];
        }
        for (int i = 0; i < z * 2; i++){
            P[i] *= Q_n[i];
            Q[i] *= Q_n[i];
        }
        FPS_pick_even_odd(P, k & 1);
        FPS_pick_even_odd(Q, 0);
        k /= 2;
        if (k == 0) break;
        FPS_extend(P);
        FPS_extend(Q);
    }
    T SP = 0, SQ = 0;
    for (int i = 0; i < z; i++) SP += P[i], SQ += Q[i];
    return SP / SQ;

    // simple
    /*
    while (k){
        auto n_Q = Q;
        for (int i = 0; i < int(Q.size()); i++){
            if (i & 1) n_Q[i] *= -1;
        }
        auto n_P = atcoder::convolution(P, n_Q);
        n_Q = atcoder::convolution(Q, n_Q);
        for (int i = 0; i < int(Q.size()); i++){
            Q[i] = n_Q[i * 2];
        }
        P.clear();
        for (int i = (k & 1); i < int(n_P.size()); i += 2){
            P.push_back(n_P[i]);
        }
        k >>= 1;
    }
    return P[0] / Q[0];
    */
}

template<class T>
// 0 = a[i] * c[0] + a[i - 1] * c[1] + a[i - 2] * c[2] + ... + a[i - d] * c[d]
// a.size() + 1 == c.size()
// c[0] = - 1 ?
// return a[k]
T Kth_Linear(long long k, std::vector<T> a, std::vector<T> c){
    int d = a.size();
    assert(d + 1 == int(c.size()));
    std::vector<T> P = atcoder::convolution(a, c);
    P.resize(d);
    return Boston_Mori(k, P, c);
}
};

#line 2 "fps/FPS_Boston_Mori.hpp"
#include <vector>
#include <atcoder/convolution>
#include <cassert>
#line 4 "fps/FPS_extend.hpp"

namespace po167{
// in  : DFT(v) (len(v) = z)
// out : DFT(v) (len(v) = 2 * z)
template<class T>
void FPS_extend(std::vector<T> &v){
    int z = v.size();
    T e = (T(atcoder::internal::primitive_root_constexpr(T::mod()))).pow(T::mod() / (2 * z));
    auto cp = v;
    atcoder::internal::butterfly_inv(cp);
    T tmp = (T)(1) / (T)(z);
    for (int i = 0; i < z; i++){
        cp[i] *= tmp;
        tmp *= e;
    }
    atcoder::internal::butterfly(cp);
    for (int i = 0; i < z; i++) v.push_back(cp[i]);
};
}
#line 3 "fps/FPS_pick_even_odd.hpp"

namespace po167{
// s.t |v| = 2 ^ s (no assert)
template<class T>
void FPS_pick_even_odd(std::vector<T> &v, int odd){
    int z = v.size() / 2;
    T half = (T)(1) / (T)(2);
    if (odd == 0){
        for (int i = 0; i < z; i++){
            v[i] = (v[i * 2] + v[i * 2 + 1]) * half;
        }
        v.resize(z);
    } else {
        T e = (T(atcoder::internal::primitive_root_constexpr(T::mod()))).pow(T::mod() / (2 * z));
        T ie = T(1) / e;
        std::vector<T> es = {half};
        while ((int)es.size() != z){
            std::vector<T> n_es((int)es.size() * 2);
            for (int i = 0; i < (int)es.size(); i++){
                n_es[i * 2] = (es[i]);
                n_es[i * 2 + 1] = (es[i] * ie);
            }
            ie *= ie;
            std::swap(n_es, es);
        }
        for (int i = 0; i < z; i ++){
            v[i] = (v[i * 2] - v[i * 2 + 1]) * es[i];
        }
        v.resize(z);
    }
}
}
#line 7 "fps/FPS_Boston_Mori.hpp"

namespace po167{
// return [x^k] P(x) / Q(x)
template<class T>
T Boston_Mori(long long k, std::vector<T> P, std::vector<T> Q){
    assert(!Q.empty() && Q[0] != 0);
    int z = 1;
    while (z < (int)std::max(P.size(), Q.size())) z *= 2;
    P.resize(z * 2, 0);
    Q.resize(z * 2, 0);
    atcoder::internal::butterfly(P);
    atcoder::internal::butterfly(Q);

    // fast
    while (k){
        // Q(-x)
        std::vector<T> Q_n(z * 2);
        for (int i = 0; i < z; i++){
            Q_n[i * 2] = Q[i * 2 + 1];
            Q_n[i * 2 + 1] = Q[i * 2];
        }
        for (int i = 0; i < z * 2; i++){
            P[i] *= Q_n[i];
            Q[i] *= Q_n[i];
        }
        FPS_pick_even_odd(P, k & 1);
        FPS_pick_even_odd(Q, 0);
        k /= 2;
        if (k == 0) break;
        FPS_extend(P);
        FPS_extend(Q);
    }
    T SP = 0, SQ = 0;
    for (int i = 0; i < z; i++) SP += P[i], SQ += Q[i];
    return SP / SQ;

    // simple
    /*
    while (k){
        auto n_Q = Q;
        for (int i = 0; i < int(Q.size()); i++){
            if (i & 1) n_Q[i] *= -1;
        }
        auto n_P = atcoder::convolution(P, n_Q);
        n_Q = atcoder::convolution(Q, n_Q);
        for (int i = 0; i < int(Q.size()); i++){
            Q[i] = n_Q[i * 2];
        }
        P.clear();
        for (int i = (k & 1); i < int(n_P.size()); i += 2){
            P.push_back(n_P[i]);
        }
        k >>= 1;
    }
    return P[0] / Q[0];
    */
}

template<class T>
// 0 = a[i] * c[0] + a[i - 1] * c[1] + a[i - 2] * c[2] + ... + a[i - d] * c[d]
// a.size() + 1 == c.size()
// c[0] = - 1 ?
// return a[k]
T Kth_Linear(long long k, std::vector<T> a, std::vector<T> c){
    int d = a.size();
    assert(d + 1 == int(c.size()));
    std::vector<T> P = atcoder::convolution(a, c);
    P.resize(d);
    return Boston_Mori(k, P, c);
}
};