#882743 (C++23) No.931 Multiplicative Convolution

• 問題: No.931 Multiplicative Convolution
• ユーザー: AC2K
• 提出日時: 2023-06-18 21:51:32
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 21,593 bytes
• コンパイル時間: 6,549 ms
• コンパイル使用メモリ: 330,796 KB
• 実行使用メモリ: 7,804 KB
• 最終ジャッジ日時: 2024-06-26 08:56:37
• 合計ジャッジ時間: 7,472 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	AC	1 ms; 5,376 KB
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-

ソースコード

#line 1 "main.cpp"
#include <atcoder/all>
#line 2 "library/src/internal/barrett.hpp"
#include <cstdint>
namespace kyopro {
namespace internal {

/**
 * @brief Barrett Reduction
 */
class barrett {
    using u32 = uint32_t;
    using u64 = uint64_t;

    u32 m;
    u64 im;

public:
    constexpr barrett() : m(0), im(0) {}
    constexpr barrett(u32 m_)
        : m(m_), im((u64) static_cast<u64>(-1) / m_ + 1) {}

    constexpr u32 get_mod() const { return m; }
    constexpr u32 reduce(int64_t a) const { return mul(a, 1); }
    constexpr u32 mul(u32 a, u32 b) const {
        if (!a || !b) {
            return 0;
        }
        u64 z = (u64)a * b;
        u64 x = (u64)(((__uint128_t)z * im) >> 64);

        u64 y = x * m;
        return (u32)(z - y + (z < y ? m : 0));
    }
};
};  // namespace internal
};  // namespace kyopro

/**
 * @ref
 * https://github.com/atcoder/ac-library/blob/master/atcoder/internal_math.hpp
 */
#line 2 "library/src/math/dynamic_modint.hpp"
#include <cassert>
#include <iostream>
#line 3 "library/src/internal/montgomery.hpp"
#include <limits>
#include <numeric>
#line 5 "library/src/internal/type_traits.hpp"
#include <typeinfo>
namespace kyopro {
namespace internal {
/*
 * @ref https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
 */
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt> struct int_least {
    static_assert(dgt <= 128);
    using type = first_enabled_t<std::enable_if<dgt <= 8, __int8_t>,
                                 std::enable_if<dgt <= 16, __int16_t>,
                                 std::enable_if<dgt <= 32, __int32_t>,
                                 std::enable_if<dgt <= 64, __int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t> >;
};
template <int dgt> struct uint_least {
    static_assert(dgt <= 128);
    using type = first_enabled_t<std::enable_if<dgt <= 8, __uint8_t>,
                                 std::enable_if<dgt <= 16, __uint16_t>,
                                 std::enable_if<dgt <= 32, __uint32_t>,
                                 std::enable_if<dgt <= 64, __uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t> >;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;
};  // namespace internal
};  // namespace kyopro
#line 6 "library/src/internal/montgomery.hpp"
namespace kyopro {
namespace internal {
using u32 = uint32_t;
using u64 = uint64_t;
using i32 = int32_t;
using i64 = int64_t;
using u128 = __uint128_t;
using i128 = __int128_t;

/**
 * @brief Montgomery Reduction
 */
template <typename T> class Montgomery {
    static constexpr int lg = std::numeric_limits<T>::digits;
    using LargeT = internal::double_size_uint_t<T>;
    T mod, r, r2, minv;
    T inv() {
        T t = 0, res = 0;
        for (int i = 0; i < lg; ++i) {
            if (~t & 1) {
                t += mod;
                res += static_cast<T>(1) << i;
            }
            t >>= 1;
        }
        return res;
    }

public:
    Montgomery() = default;
    constexpr T get_mod() { return mod; }

    void set_mod(T m) {
        assert(m);
        assert(m & 1);

        mod = m;

        r = (-static_cast<T>(mod)) % mod;
        r2 = (-static_cast<LargeT>(mod)) % mod;
        minv = inv();
    }

    T reduce(LargeT x) const {
        u64 res =
            (x + static_cast<LargeT>(static_cast<T>(x) * minv) * mod) >> lg;

        if (res >= mod) res -= mod;
        return res;
    }

    T generate(LargeT x) { return reduce(x * r2); }

    T mul(T x, T y) { return reduce((LargeT)x * y); }
};
};  // namespace internal
};  // namespace kyopro
#line 6 "library/src/math/dynamic_modint.hpp"
namespace kyopro {
template <int id = -1> class barrett_modint {
    using u32 = uint32_t;
    using u64 = uint64_t;

    using i32 = int32_t;
    using i64 = int64_t;
    using br = internal::barrett;

    static br brt;
    static u32 mod;
    u32 v;

public:
    static void set_mod(u32 mod_) {
        brt = br(mod_);
        mod = mod_;
    }

public:
    explicit constexpr barrett_modint() : v(0) { assert(mod); }
    explicit constexpr barrett_modint(i64 v_) : v(brt.reduce(v_)) {
        assert(mod);
    }

    u32 val() const { return v; }
    static u32 get_mod() { return mod; }
    using mint = barrett_modint<id>;

    constexpr mint& operator=(i64 r) {
        v = brt.reduce(r);
        return (*this);
    }
    constexpr mint& operator+=(const mint& r) {
        v += r.v;
        if (v >= mod) {
            v -= mod;
        }
        return (*this);
    }
    constexpr mint& operator-=(const mint& r) {
        v += mod - r.v;
        if (v >= mod) {
            v -= mod;
        }

        return (*this);
    }
    constexpr mint& operator*=(const mint& r) {
        v = brt.mul(v, r.v);
        return (*this);
    }

    constexpr mint operator+(const mint& r) const { return mint(*this) += r; }
    constexpr mint operator-(const mint& r) const { return mint(*this) -= r; }
    constexpr mint operator*(const mint& r) const { return mint(*this) *= r; }

    constexpr mint& operator+=(i64 r) { return (*this) += mint(r); }
    constexpr mint& operator-=(i64 r) { return (*this) -= mint(r); }
    constexpr mint& operator*=(i64 r) { return (*this) *= mint(r); }

    friend mint operator+(i64 l, const mint& r) { return mint(l) += r; }
    friend mint operator+(const mint& l, i64 r) { return mint(l) += r; }
    friend mint operator-(i64 l, const mint& r) { return mint(l) -= r; }
    friend mint operator-(const mint& l, i64 r) { return mint(l) -= r; }
    friend mint operator*(i64 l, const mint& r) { return mint(l) *= r; }
    friend mint operator*(const mint& l, i64 r) { return mint(l) += r; }

    friend std::ostream& operator<<(std::ostream& os, const mint& mt) {
        os << mt.val();
        return os;
    }
    friend std::istream& operator>>(std::istream& is, mint& mt) {
        i64 v_;
        is >> v_;
        mt = v_;
        return is;
    }
    template <typename T> mint pow(T e) const {
        mint res(1), base(*this);

        while (e) {
            if (e & 1) {
                res *= base;
            }
            e >>= 1;
            base *= base;
        }
        return res;
    }
    mint inv() const { return pow(mod - 2); }

    mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
    mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
    mint& operator/=(i64 r) { return (*this) /= mint(r); }
    friend mint operator/(const mint& l, i64 r) { return mint(l) /= r; }
    friend mint operator/(i64 l, const mint& r) { return mint(l) /= r; }
};
};  // namespace kyopro
template <int id>
typename kyopro::barrett_modint<id>::u32 kyopro::barrett_modint<id>::mod;
template <int id>
typename kyopro::barrett_modint<id>::br kyopro::barrett_modint<id>::brt;

namespace kyopro {
template <typename T, int id = -1> class dynamic_modint {
    using LargeT = internal::double_size_uint_t<T>;
    static T mod;
    static internal::Montgomery<T> mr;

public:
    static void set_mod(T mod_) {
        mr.set_mod(mod_);
        mod = mod_;
    }

    static T get_mod() { return mod; }

private:
    T v;

public:
    dynamic_modint(T v_ = 0) {
        assert(mod);
        v = mr.generate(v_);
    }
    T val() const { return mr.reduce(v); }

    using mint = dynamic_modint<T, id>;
    mint& operator+=(const mint& r) {
        v += r.v;
        if (v >= mr.get_mod()) {
            v -= mr.get_mod();
        }

        return (*this);
    }

    mint& operator-=(const mint& r) {
        v += mr.get_mod() - r.v;
        if (v >= mr.get_mod) {
            v -= mr.get_mod();
        }

        return (*this);
    }

    mint& operator*=(const mint& r) {
        v = mr.mul(v, r.v);
        return (*this);
    }

    mint operator+(const mint& r) { return mint(*this) += r; }
    mint operator-(const mint& r) { return mint(*this) -= r; }
    mint operator*(const mint& r) { return mint(*this) *= r; }

    mint& operator=(const T& v_) {
        (*this) = mint(v_);
        return (*this);
    }

    friend std::ostream& operator<<(std::ostream& os, const mint& mt) {
        os << mt.val();
        return os;
    }
    friend std::istream& operator>>(std::istream& is, mint& mt) {
        T v_;
        is >> v_;
        mt = v_;
        return is;
    }
    template <typename P> mint pow(P e) const {
        assert(e >= 0);
        mint res(1), base(*this);

        while (e) {
            if (e & 1) {
                res *= base;
            }
            e >>= 1;
            base *= base;
        }
        return res;
    }
    mint inv() const { return pow(mod - 2); }

    mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
    mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
    mint& operator/=(T r) { return (*this) /= mint(r); }
    friend mint operator/(const mint& l, T r) { return mint(l) /= r; }
    friend mint operator/(T l, const mint& r) { return mint(l) /= r; }
};
};  // namespace kyopro
template <typename T, int id> T kyopro::dynamic_modint<T, id>::mod;
template <typename T, int id>
kyopro::internal::Montgomery<T> kyopro::dynamic_modint<T, id>::mr;

/**
 * @brief 動的modint
 * @docs docs/math/dynamic_modint.md
 */
#line 2 "library/src/math/rho.hpp"
#include <algorithm>
#include <vector>
#line 3 "library/src/math/gcd.hpp"
#include <tuple>
namespace kyopro {
template <typename T> constexpr T inline _gcd(T a, T b) {
    assert(a >= 0 && b >= 0);
    if (a == 0 || b == 0) return a + b;
    int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));
    a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);
    while (a != b) {
        if (!a || !b) {
            return a + b;
        }
        if (a >= b) {
            a -= b;
            a >>= __builtin_ctzll(a);
        } else {
            b -= a;
            b >>= __builtin_ctzll(b);
        }
    }

    return a << d;
}
template <typename T> constexpr T ext_gcd(T a, T b, T& x, T& y) {
    x = 1, y = 0;
    T nx = 0, ny = 1;
    while (b) {
        T q = a / b;
        std::tie(a, b) = std::pair<T, T>{b, a % b};
        std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
        std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
    }
    return a;
}
};  // namespace kyopro
#line 3 "library/src/math/miller.hpp"
namespace kyopro {

/**
 * @brief MillerRabin素数判定法
 */
class miller {
    using i128 = __int128_t;
    using u128 = __uint128_t;
    using u64 = uint64_t;
    using u32 = uint32_t;

    template <typename T, typename mint, const int bases[], int length>
    static constexpr bool miller_rabin(T n) {
        T d = n - 1;

        while (~d & 1) {
            d >>= 1;
        }

        const T rev = n - 1;
        if (mint::get_mod() != n) {
            mint::set_mod(n);
        }
        for (int i = 0; i < length; ++i) {
            if (n <= bases[i]) {
                return true;
            }
            T t = d;
            mint y = mint(bases[i]).pow(t);

            while (t != n - 1 && y.val() != 1 && y.val() != rev) {
                y *= y;
                t <<= 1;
            }

            if (y.val() != rev && (~t & 1)) return false;
        }
        return true;
    }
    // 底
    static constexpr int bases_int[3] = {2, 7, 61};
    static constexpr int bases_ll[7] = {2,      325,     9375,      28178,
                                        450775, 9780504, 1795265022};

public:
    template <typename T> static constexpr bool is_prime(T n) {
        if (n < 2) {
            return false;
        } else if (n == 2) {
            return true;
        } else if (~n & 1) {
            return false;
        };
        if (std::numeric_limits<T>::digits < 32 || n <= 1 << 30) {
            return miller_rabin<T, dynamic_modint<std::make_unsigned_t<T>>,
                                bases_int, 3>(n);
        } else {
            return miller_rabin<T, dynamic_modint<std::make_unsigned_t<T>>,
                                bases_ll, 7>(n);
        }
        return false;
    }
};
};  // namespace kyopro

/**
 * @docs docs/math/miller.md
 */
#line 2 "library/src/random/xor_shift.hpp"
#include <chrono>
#line 4 "library/src/random/xor_shift.hpp"
#include <random>

namespace kyopro {
struct xor_shift32 {
    uint32_t rng;
    constexpr explicit xor_shift32(uint32_t seed) : rng(seed) {}
    explicit xor_shift32()
        : rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    constexpr uint32_t operator()() {
        rng ^= rng << 13;
        rng ^= rng >> 17;
        rng ^= rng << 5;
        return rng;
    }
};

struct xor_shift {
    uint64_t rng;
    constexpr xor_shift(uint64_t seed) : rng(seed) {}
    explicit xor_shift()
        : rng(std::chrono::steady_clock::now().time_since_epoch().count()) {}
    constexpr uint64_t operator()() {
        rng ^= rng << 13;
        rng ^= rng >> 7;
        rng ^= rng << 17;
        return rng;
    }
};

};  // namespace kyopro

/**
 * @brief xor shift
 */
#line 7 "library/src/math/rho.hpp"
namespace kyopro {

/**
 * @brief Pollard Rho 素因数分解法
 */
class rho {
    using i128 = __int128_t;
    using u128 = __uint128_t;
    using u64 = uint64_t;
    using u32 = uint32_t;

    template <typename mint> static u64 find_factor(u64 n) {
        xor_shift32 rng(2023);

        if (~n & 1uL) {
            return 2;
        }
        if (kyopro::miller::is_prime(n)) {
            return n;
        }

        if (mint::get_mod() != n) {
            mint::set_mod(n);
        }
        while (1) {
            u64 c = rng();
            const auto f = [&](mint x) -> mint { return x * x + c; };
            mint x = rng();
            mint y = f(x);
            u64 d = 1;
            while (d == 1) {
                d = _gcd<long long>(
                    std::abs((long long)x.val() - (long long)y.val()), n);
                x = f(x);
                y = f(f(y));
            }
            if (1 < d && d < n) {
                return d;
            }
        }
        exit(0);
    }
    template <typename mint> static std::vector<u64> rho_fact(u64 n) {
        if (n < 2) {
            return {};
        }
        if (kyopro::miller::is_prime(n)) {
            return {n};
        }
        std::vector<u64> v;
        std::vector<u64> st{n};
        while (st.size()) {
            u64& m = st.back();
            if (kyopro::miller::is_prime(m)) {
                v.emplace_back(m);
                st.pop_back();
            } else {
                u64 d = find_factor<mint>(m);
                m /= d;
                st.emplace_back(d);
            }
        }
        return v;
    }

public:
    static std::vector<u64> factorize(u64 n) {
        if (n < 2) {
            return {};
        }
        auto v = (n < (1uL << 31) ? rho_fact<dynamic_modint<u32>>(n)
                                  : rho_fact<dynamic_modint<u64>>(n));
        std::sort(v.begin(), v.end());
        return v;
    }

    static std::vector<std::pair<u64, int>> exp_factorize(u64 n) {
        std::vector<u64> pf = factorize(n);
        if (pf.empty()) {
            return {};
        }
        std::vector<std::pair<u64, int>> res;
        res.emplace_back(pf.front(), 1);
        for (int i = 1; i < (int)pf.size(); i++) {
            if (res.back().first == pf[i]) {
                res.back().second++;
            } else {
                res.emplace_back(pf[i], 1);
            }
        }

        return res;
    }

    static std::vector<u64> enumerate_divisor(u64 n) {
        std::vector<std::pair<u64, int>> pf = rho::exp_factorize(n);
        std::vector<u64> divisor{1};
        for (auto [p, e] : pf) {
            u64 pow = p;
            int sz = divisor.size();
            for (int i = 0; i < e; ++i) {
                for (int j = 0; j < sz; ++j)
                    divisor.emplace_back(divisor[j] * pow);
                pow *= p;
            }
        }

        return divisor;
    }
};
};  // namespace kyopro

/**
 * @docs docs/math/rho.md
 */
#line 5 "library/src/math/primitive_root.hpp"
namespace kyopro {

/**
 * @brief 原始根
 */
inline uint64_t primitive_root(uint64_t p) {
    if (p == 2) return 1;
    auto pf = kyopro::rho::factorize(p - 1);
    pf.erase(std::unique(pf.begin(), pf.end()), pf.end());
    for (auto& q : pf) {
        q = (p - 1) / q;
    }
    using ull = unsigned long long;
    if (dynamic_modint<uint64_t>::get_mod() != p) {
        dynamic_modint<uint64_t>::set_mod(p);
    }
    xor_shift rng(2023);
    while (1) {
        dynamic_modint<uint64_t> g(rng());
        if (g.val() == 0) continue;
        bool is_ok = true;

        for (auto q : pf) {
            if (dynamic_modint<uint64_t>(g).pow(q).val() == 1) {
                is_ok = false;
                break;
            }
        }
        if (is_ok) {
            return g.val();
        }
    }
}
};  // namespace kyopro
#line 2 "library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
namespace kyopro {

/**
 *  整数の入出力
 */
template <typename T> constexpr inline void readint(T& a) {
    a = 0;
    bool is_negative = false;
    char c = getchar_unlocked();
    while (isspace(c)) {
        c = getchar_unlocked();
    }
    if (c == '-') is_negative = true, c = getchar_unlocked();
    while (isdigit(c)) {
        a = 10 * a + (c - '0');
        c = getchar_unlocked();
    }
    if (is_negative) a *= -1;
}
template <typename Head, typename... Tail>
constexpr inline void readint(Head& head, Tail&... tail) {
    readint(head);
    readint(tail...);
}

template <typename T> void write_int(T a) {
    if (!a) {
        putchar_unlocked('0');
        putchar_unlocked('\n');
        return;
    }
    if (a < 0) putchar_unlocked('-'), a *= -1;
    char s[37];
    int now = 37;
    while (a) {
        s[--now] = (char)'0' + a % 10;
        a /= 10;
    }
    while (now < 37) putchar_unlocked(s[now++]);
}
template <typename T> constexpr inline void putint(T a) {
    if (!a) {
        putchar_unlocked('0');
        putchar_unlocked('\n');
        return;
    }
    if (a < 0) putchar_unlocked('-'), a *= -1;
    char s[37];
    int now = 37;
    while (a) {
        s[--now] = (char)'0' + a % 10;
        a /= 10;
    }
    while (now < 37) putchar_unlocked(s[now++]);
    putchar_unlocked('\n');
}
template <typename Head, typename... Tail>
constexpr inline void putint(Head head, Tail... tail) {
    putint(head);
    putint(tail...);
}

/**
 * 文字列の入出力
 */

void readstr(std::string& str) {
    char c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
    while (!isspace(c)) {
        str += c;
        c = getchar_unlocked();
    }
}
void putstr(const std::string& str) {
    for (auto c : str) {
        putchar_unlocked(c);
    }
    putchar_unlocked('\n');
}

};  // namespace kyopro

/**
 * @brief fastIO
 */
#line 2 "library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define all(x) (x).begin(), (x).end()
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;
constexpr ld eps = 1e-6;
const long double pi = acos(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = {1, 0, -1, 0};
constexpr int dy[] = {0, 1, 0, -1};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
    return a > b && (a = b, true);
}
#line 6 "main.cpp"
#define debug(x)                                    \
    std::cout << #x << " : ";                       \
    for (auto __ : x) std::cout << __.val() << ' '; \
    std::cout << std::endl;

using namespace std;
using namespace atcoder;
using namespace kyopro;

using mint = atcoder::modint998244353;

int main() {
    int p;
    readint(p);

    int g = primitive_root(p);
    // putint(g);

    vector<mint> a(p), b(p);
    for (int i = 1; i < p; ++i) readint(a[i]);
    for (int i = 1; i < p; ++i) readint(b[i]);

    vector<mint> ap(p - 1), bp(p - 1);

    vector<int> pow(p);
    {
        for (int e = 0, pw = 1; e <= p; ++e) {
            pow[e] = pw;
            pw = (ll)pw * g % p;
        }
    }

    for (int i = 0; i < p - 1; ++i) {
        ap[i] = a[pow[i]];
        bp[i] = b[pow[i]];
    }
    // debug(ap) debug(bp);

    vector<mint> cp = convolution(ap, bp);
    // debug(cp);

    vector<mint> c(p);
    for (int i = p - 1; i < (int)cp.size(); ++i) {
        cp[i - p + 1] += cp[i];
    }
    // debug(cp);
    for (int i = 0; i < p - 1; ++i) {
        c[pow[i]] = cp[i];
    }
    // debug(c);
    for (int i = 1; i < p; ++i) putint(c[i].val());
}