結果

問題 No.931 Multiplicative Convolution
コンテスト
ユーザー iastm
提出日時 2026-04-14 02:29:28
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 6,514 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,861 ms
コンパイル使用メモリ 245,512 KB
実行使用メモリ 7,948 KB
最終ジャッジ日時 2026-04-14 02:29:36
合計ジャッジ時間 5,525 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int64_t kotone::least_primitive_root(int64_t)':
main.cpp:208:1: warning: control reaches end of non-void function [-Wreturn-type]
  208 | }
      | ^

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <atcoder/convolution>
// #include <kotone/prime>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_PRIME_HPP
#define KOTONE_PRIME_HPP 1

#include <vector>
#include <algorithm>
#include <bit>
#include <numeric>
#include <cassert>
// #include <kotone/random>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_RANDOM_HPP
#define KOTONE_RANDOM_HPP 1

#include <random>

namespace kotone {

// Returns a random unsigned 64-bit integer.
uint64_t randint() {
    static std::random_device rd;
    static std::mt19937_64 gen(rd());
    return gen();
}

// Reference: https://codeforces.com/blog/entry/62393
uint64_t splitmix64(uint64_t x) noexcept {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

// A randomized hash for integers.
struct randomized_hash {
    std::size_t operator()(uint64_t x) const {
        static const uint64_t SEED = randint();
        return splitmix64(x ^ SEED);
    }
};

}  // namespace kotone

#endif  // KOTONE_RANDOM_HPP
// #include <kotone/mod_math>
// https://github.com/amiast/cpp-utility

#ifndef KOTONE_MOD_MATH_HPP
#define KOTONE_MOD_MATH_HPP 1

#include <concepts>
#include <cassert>

namespace kotone {

// Returns the non-negative remainder produced from dividing `n` by `m`.
// Requires `m > 0`.
template <std::signed_integral T> uint64_t mod(T n, uint64_t m) {
    assert(m > 0u);
    if (n >= 0) return uint64_t(n) % m;
    if (m < 1ULL << 63) {
        int64_t sm = m;
        return (n % sm + sm) % sm;
    }
    if (n == -1LL << 63) return m - (1ULL << 63);
    return m - -n;
}

// Returns the non-negative remainder produced from dividing `n` by `m`.
// Requires `m > 0`.
template <std::unsigned_integral T> uint64_t mod(T n, uint64_t m) {
    assert(m > 0u);
    return n % m;
}

// Returns `(a + b) % m`.
// Requires `m > 0`.
template <std::integral S, std::integral T> uint64_t sum_mod(S a, T b, uint64_t m) {
    uint64_t ua = mod(a, m), ub = mod(b, m);
    uint64_t result = ua + ub;
    if (result < ua) result -= m;
    if (result >= m) result -= m;
    return result;
}

// Returns `a * b % m`.
// Requires `m > 0`.
// Requires compiler-provided type `__int128`.
template <std::integral S, std::integral T> uint64_t prod_mod(S a, T b, uint64_t m) {
    uint64_t ua = mod(a, m), ub = mod(b, m);
    return __int128(ua) * ub % m;
}

// Returns `pow(n, k) % m`.
// Returns `1 % m` if `n == k == 0`.
// Requires `m > 0`.
// Requires compiler-provided type `__int128`.
template<std::integral T> uint64_t pow_mod(T n, uint64_t k, uint64_t m) {
    assert(m > 0u);
    if (k == 0) return m > 1u;
    uint64_t un = mod(n, m);
    uint64_t result = 1 % m;
    while (k) {
        if (k & 1u) result = prod_mod(result, un, m);
        un = prod_mod(un, un, m);
        k >>= 1;
    }
    return result;
}

}

#endif  // KOTONE_MOD_MATH_HPP

namespace kotone {

// Retuens a `bool` indicating whether `n` is prime.
// Requires compiler-provided type `__int128`.
bool is_prime(int64_t n) {
    constexpr static int bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    if (n <= 2) return n == 2;
    if (~n & 1) return false;
    int64_t s = std::bit_width(uint64_t((n - 1) & -(n - 1))) - 1;
    int64_t d = (n - 1) >> s;
    for (int a : bases) {
        if (a >= n) continue;
        int64_t x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool flag = true;
        for (int t = 0; t < s - 1; t++) {
            x = prod_mod(x, x, n);
            if (x == n - 1) {
                flag = false;
                break;
            }
        }
        if (flag) return false;
    }
    return true;
}

// Returns a factor of composite number `n`.
// Requires `n` to be a positive composite number.
// Requires compiler-provided type `__int128`.
int64_t pollards_rho(int64_t n) {
    assert(n >= 4);
    if (n % 2 == 0) return 2;
    while (true) {
        int64_t b = randint() % (n - 3) + 1;
        auto g = [n, b](int64_t x) {
            return sum_mod(prod_mod(x, x, n), b, n);
        };
        int64_t x = randint() % n;
        int64_t y = x, d = 1;
        while (d == 1) {
            x = g(x);
            y = g(g(y));
            d = std::gcd(std::abs(x - y), n);
        }
        if (d != n) return d;
    }
}

// Returns a vector containing all prime factors of `n`.
// The order of factors is undefined.
// Requires `n` to be a positive integer.
// Requires compiler-provided type `__int128`.
std::vector<int64_t> factorize(int64_t n) {
    assert(n > 0);
    auto rec = [&](auto &rec, int64_t n, std::vector<int64_t> &vec) {
        if (n == 1) return;
        if (is_prime(n)) {
            vec.push_back(n);
            return;
        }
        int64_t d = pollards_rho(n);
        rec(rec, d, vec);
        rec(rec, n / d, vec);
    };
    std::vector<int64_t> result;
    rec(rec, n, result);
    return result;
}

// Returns the least primitive root of prime `p`.
// Requires `p` to be a prime.
// Requires compiler-provided type `__int128`.
int64_t least_primitive_root(int64_t p) {
    std::vector<int64_t> factors = factorize(p - 1);
    std::sort(factors.begin(), factors.end());
    factors.erase(std::unique(factors.begin(), factors.end()), factors.end());
    for (int64_t n = 1; n < p; n++) {
        bool flag = true;
        for (int64_t q : factors) {
            if (pow_mod(n, (p - 1) / q, p) == 1) {
                flag = false;
                break;
            }
        }
        if (flag) return n;
    }
}

}  // namespace kotone

#endif  // KOTONE_PRIME_HPP

using mint = atcoder::modint998244353;

int main() {
    int P;
    std::cin >> P;
    std::vector<int> A(P), B(P);
    for (int i = 1; i < P; i++) std::cin >> A[i];
    for (int i = 1; i < P; i++) std::cin >> B[i];

    int g = kotone::least_primitive_root(P);
    int64_t acc = 1;
    std::vector<int> exp_to_int(P - 1);
    for (int i = 0; i < P - 1; i++) {
        exp_to_int[i] = acc;
        acc *= g;
        acc %= P;
    }

    std::vector<mint> pa(P - 1), pb(P - 1);
    for (int i = 0; i < P - 1; i++) pa[i] = A[exp_to_int[i]];
    for (int i = 0; i < P - 1; i++) pb[i] = B[exp_to_int[i]];
    std::vector<mint> prod = atcoder::convolution(pa, pb);

    std::vector<mint> result(P);
    for (int i = 0; i < P * 2 - 3; i++) result[exp_to_int[i % (P - 1)]] += prod[i];
    for (int i = 1; i < P; i++) std::cout << result[i].val() << ' ';
    std::cout << std::endl;
}
0