test/fps/inv.test.cpp

• View this file on GitHub
• Last update: 2024-06-19 01:08:42+09:00
• Problem: https://judge.yosupo.jp/problem/inv_of_formal_power_series

Depends on

• fps/FPS_inv.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/inv_of_formal_power_series"
#include "../../fps/FPS_inv.hpp"

#include <vector>
#include <iostream>
#include <atcoder/modint>

int main(){
    using mint = atcoder::modint998244353;
    int N;
    std::cin >> N;
    std::vector<mint> A(N);
    for (int i = 0; i < N; i++){
        int a;
        std::cin >> a;
        A[i] = a;
    }
    A = po167::FPS_inv(A, N);
    for (int i = 0; i < N; i++){
        std::cout << A[i].val() << " ";
    }
    std::cout << "\n";
}

#line 1 "test/fps/inv.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/inv_of_formal_power_series"
#line 2 "fps/FPS_inv.hpp"
#include <vector>
#include <atcoder/convolution>

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 3 "test/fps/inv.test.cpp"

#line 5 "test/fps/inv.test.cpp"
#include <iostream>
#include <atcoder/modint>

int main(){
    using mint = atcoder::modint998244353;
    int N;
    std::cin >> N;
    std::vector<mint> A(N);
    for (int i = 0; i < N; i++){
        int a;
        std::cin >> a;
        A[i] = a;
    }
    A = po167::FPS_inv(A, N);
    for (int i = 0; i < N; i++){
        std::cout << A[i].val() << " ";
    }
    std::cout << "\n";
}

Back to top page