結果

問題 No.754 畳み込みの和
ユーザー PachicobuePachicobue
提出日時 2018-12-02 00:27:03
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 309 ms / 5,000 ms
コード長 4,792 bytes
コンパイル時間 3,409 ms
コンパイル使用メモリ 212,652 KB
実行使用メモリ 12,884 KB
最終ジャッジ日時 2023-09-09 10:45:28
合計ジャッジ時間 4,583 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 304 ms
12,840 KB
testcase_01 AC 306 ms
12,788 KB
testcase_02 AC 309 ms
12,884 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
constexpr ll MOD = 1000000007;
constexpr std::size_t PC(ull v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<std::size_t>(v * 0x0101010101010101ULL >> 56 & 0x7f); }
constexpr std::size_t LG(ull v) { return v == 0 ? 0 : (v--, v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PC(v)); }
constexpr ull SZ(const ull v) { return 1ULL << LG(v); }
template <typename T>
constexpr std::pair<T, T> extgcd(const T a, const T b)
{
    if (b == 0) { return std::pair<T, T>{1, 0}; }
    const auto p = extgcd(b, a % b);
    return {p.second, p.first - p.second * (a / b)};
}
template <typename T>
constexpr T inverse(const T a, const T mod = MOD) { return (mod + extgcd(a, mod).first % mod) % mod; }
template <typename T, T mod = 924844033, T root = 5>
class NumberTheoreticTransformation
{
private:
    NumberTheoreticTransformation() = delete;
    static T add(const T x, const T y) { return (x + y < mod) ? x + y : x + y - mod; }
    static T mul(const T x, const T y) { return (x * y) % mod; }
    static T power(const T x, const T n) { return n == 0 ? (T)1 : n % 2 == 1 ? mul(power(x, n - 1), x) : power(mul(x, x), n / 2); }
    static T inverse(const T x) { return ::inverse(x, mod); }

public:
    static void ntt(std::vector<T>& a, const bool rev = false)
    {
        const std::size_t size = a.size(), height = LG(size);
        for (std::size_t i = 0, j = 0; i < size; i++, j = 0) {
            for (std::size_t k = 0; k < height; k++) { j |= (i >> k & 1) << (height - 1 - k); }
            if (i < j) { std::swap(a[i], a[j]); }
        }
        for (std::size_t i = 1; i < size; i <<= 1) {
            T w = power(root, (mod - 1) / (i * 2));
            if (rev) { w = inverse(w); }
            for (std::size_t j = 0; j < size; j += i * 2) {
                T wn = 1;
                for (std::size_t k = 0; k < i; k++, wn = mul(wn, w)) {
                    const T s = a[j + k + 0], t = mul(a[j + k + i], wn);
                    a[j + k + 0] = add(s, t), a[j + k + i] = add(s, mod - t);
                }
            }
        }
        if (not rev) { return; }
        const T v = inverse(size);
        for (std::size_t i = 0; i < size; i++) { a[i] = mul(a[i], v); }
    }
    static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b)  // ans[i] = \sum_{A+B = i} a[A]*b[B]
    {
        const std::size_t size = a.size() + b.size() - 1, t = (std::size_t)SZ(size);
        std::vector<T> A(t, 0), B(t, 0);
        for (std::size_t i = 0; i < a.size(); i++) { A[i] = a[i]; }
        for (std::size_t i = 0; i < b.size(); i++) { B[i] = b[i]; }
        ntt(A), ntt(B);
        for (std::size_t i = 0; i < t; i++) { A[i] = mul(A[i], B[i]); }
        ntt(A, true);
        A.resize(size);
        return A;
    }
};
template <typename T>
class GarnerNumberTheoreticTransformation
{
private:
    static constexpr T mod1 = 167772161;
    static constexpr T mod2 = 469762049;
    static constexpr T mod3 = 1224736769;
    static constexpr T mod1_inv_mod2 = inverse(mod1, mod2);
    static constexpr T mod1mod2_inv_mod3 = inverse(mod1 * mod2, mod3);
    using NTT1 = NumberTheoreticTransformation<T, mod1, 3>;
    using NTT2 = NumberTheoreticTransformation<T, mod2, 3>;
    using NTT3 = NumberTheoreticTransformation<T, mod3, 3>;
    GarnerNumberTheoreticTransformation() = delete;

public:
    static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b, const T mod)  // ans[i] = \sum_{A+B = i} a[A]*b[B]
    {
        const auto x = NTT1::convolute(a, b), y = NTT2::convolute(a, b), z = NTT3::convolute(a, b);
        const std::size_t size = x.size();
        std::vector<T> ans(size);
        const T mod1mod2_mod = mod1 * mod2 % mod;
        for (std::size_t i = 0; i < size; i++) {
            T v1 = (y[i] - x[i]) * mod1_inv_mod2 % mod2;
            if (v1 < 0) { v1 += mod2; }
            T v2 = (z[i] - (x[i] + mod1 * v1) % mod3) * mod1mod2_inv_mod3 % mod3;
            if (v2 < 0) { v2 += mod3; }
            T c = (x[i] + mod1 * v1 + mod1mod2_mod * v2) % mod;
            if (c < 0) { c += mod; }
            ans[i] = c;
        }
        return ans;
    }
};

int main()
{
    int N;
    std::cin >> N;
    std::vector<ll> a(N + 1), b(N + 1);
    for (int i = 0; i <= N; i++) { std::cin >> a[i]; }
    for (int i = 0; i <= N; i++) { std::cin >> b[i]; }
    const auto c = GarnerNumberTheoreticTransformation<ll>::convolute(a, b, MOD);
    ll ans = 0;
    for (int i = 0; i <= N; i++) { (ans += c[i]) %= MOD; }
    std::cout << ans << std::endl;
    return 0;
}
0