#878135 (C++23) No.2272 多項式乗算 mod 258280327

提出ソース

結果

問題	No.2272 多項式乗算 mod 258280327
ユーザー	tsugutsugu
提出日時	2023-06-04 23:32:00
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	11,413 bytes
コンパイル時間	4,434 ms
コンパイル使用メモリ	287,972 KB
実行使用メモリ	28,560 KB
最終ジャッジ日時	2024-06-09 04:13:38
合計ジャッジ時間	7,674 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	1 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	1 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	1 ms 6,940 KB
testcase_14	AC	1 ms 6,944 KB
testcase_15	AC	1 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	2 ms 6,948 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	9 ms 6,944 KB
testcase_25	AC	35 ms 6,944 KB
testcase_26	AC	34 ms 6,940 KB
testcase_27	AC	76 ms 6,944 KB
testcase_28	AC	77 ms 6,944 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.hpp"
#else
#define debug(...) 1
#endif

using u64 = unsigned long long;

struct xorshift {
    using u32 = uint32_t;
    u32 x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    xorshift(u32 seed = 0) { z ^= seed; }
    u32 operator()() {
        u32 t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }
};

unsigned long long modpow128(unsigned long long a, unsigned long long n, unsigned long long mod) {
    unsigned long long res = 1;
    while (n > 0) {
        if (n & 1) {
            res = (__uint128_t) res * a % mod;
        }
        a = (__uint128_t) a * a % mod;
        n >>= 1;
    }
    return res;
}
const vector<int> primes_small = {2, 7, 61};
const vector<int> primes_large = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool MillerRabin(long long n) {
    if (n == 1) {
        return false;
    } else if (n == 2) {
        return true;
    } else if (n % 2 == 0) {
        return false;
    }
    long long d = n - 1, s = 0;
    while (d % 2 == 0) {
        s++;
        d >>= 1;
    }
    vector<int> primes = (n < 4759123141LL ? primes_small : primes_large);
    for (int p : primes) {
        if (p >= n) {
            break;
        }
        bool composite = true;
        __int128_t x = modpow128(p, d, n);
        composite &= (x != 1);
        for (int i = 0; i < s; i++) {
            composite &= (x != n - 1);
            x = (x * x) % n;
        }
        if (composite) {
            return false;
        }
    }
    return true;
}
long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}
long long find_prime_factor(long long N) {
    if (~N & 1) {
        return 2;
    }
    if (MillerRabin(N)) {
        return N;
    }
    random_device seed_gen;
    xorshift rnd(seed_gen());
    long long beg = 0;
    auto f = [&] (long long A, long long d) -> long long { return ((__int128_t) A * A + d) % N; };
    while (1) {
        long long d = rnd();
        long long x = ++beg, y = f(x, d);
        while (1) {
            long long p = gcd(N, abs(x - y));
            if (p == 0 || p == N) {
                break;
            }
            if (p != 1) {
                return p;
            }
            x = f(x, d);
            y = f(f(y, d), d);
        }
    }
}
vector<long long> prime_factorize(long long N) {
    if (N == 1) return {};
    long long p = find_prime_factor(N);
    if (p == N) {
        return {p};
    }
    vector<long long> left = prime_factorize(p);
    vector<long long> right = prime_factorize(N / p);
    left.insert(left.end(), right.begin(), right.end());
    sort(left.begin(), left.end());
    return left;
}

long long primitive_root(long long p) {
    if (p == 2) return 1;
    if (p == 167772161) return 3;
    if (p == 469762049) return 3;
    if (p == 754974721) return 11;
    if (p == 998244353) return 3;
    vector<long long> v = prime_factorize(p - 1);
    v.erase(unique(v.begin(), v.end()), v.end());
    random_device seed_gen;
    mt19937_64 mt(seed_gen());
    while (1) {
        unsigned long long x = mt() % p;
        if (x == 0) {
            continue;
        }
        if (modpow128(x, p - 1, p) == 1) {
            bool ok = true;
            for (int i = 0; i < (int) v.size(); i++) {
                if (modpow128(x, (p - 1) / v[i], p) == 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                assert(modpow128(x, p - 1, p) == 1);
                return x;
            }
        }
    }
}

long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    long long d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
long long mod_inv(long long a, long long m) {
    long long x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
long long Garner(vector<long long> R, vector<long long> M, long long mod) {
    assert(R.size() == M.size());
    M.push_back(mod);
    vector<long long> coeffs((int) M.size(), 1), constants((int) M.size(), 0);
    for (int i = 0; i < (int) R.size(); i++) {
        long long v = (R[i] - constants[i]) * mod_inv(coeffs[i], M[i]) % M[i];
        if (v < 0) {
            v += M[i];
        }
        for (int j = i + 1; j < (int) M.size(); j++) {
            (constants[j] += coeffs[j] * v) %= M[j];
            (coeffs[j] *= M[i]) %= M[j];
        }
    }
    return constants.back();
}

template <int m>
struct modint {
    unsigned int v = 0;
    static constexpr long long mod() { return m; }
    static constexpr unsigned int umod() { return m; }
    unsigned int val() { return v; }
    modint() : v(0) {}
    modint(long long _v) {
        long long x = (long long)(_v % umod());
        if (x < 0) {
            x += umod();
        }
        v = (unsigned int) x;
    }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint(const modint &rhs) { v = rhs.v; }
    modint &operator+=(const modint &rhs) {
        v += rhs.v;
        if (v >= umod()) {
            v -= umod();
        }
        return *this;
    }
    modint operator+(const modint &rhs) const {
        return modint(*this) += rhs;
    }
    modint &operator-=(const modint &rhs) {
        v -= rhs.v;
        if (v >= umod()) {
            v += umod();
        }
        return *this;
    }
    modint operator-(const modint &rhs) const {
        return modint(*this) -= rhs;
    }
    modint &operator*=(const modint &rhs) {
        unsigned long long x = v;
        x *= rhs.v;
        v = (unsigned int) (x % umod());
        return *this;
    }
    modint operator*(const modint &rhs) const {
        return modint(*this) *= rhs;
    }
    template <typename T>
    modint pow(T n) const {
        modint x = *this, ret = 1;
        while (n) {
            if (n & 1) ret *= x;
            x *= x;
            n >>= 1;
        }
        return ret;
    }
    modint inv() const {
        return pow(umod() - 2);
    }
    modint &operator/=(const modint &rhs) {
        *this *= rhs.inv();
        return *this;
    }
    modint operator/(const modint &rhs) const {
        return modint(*this) /= rhs;
    }
    friend istream &operator>>(istream &is, modint &v) {
        long long x;
        is >> x;
        v.v = x;
        return is;
    }
    friend ostream &operator<<(ostream &os, modint &v) {
        return os << v.v;
    }
};
constexpr int md = 998244353;
// constexpr int md = 1000000007;
vector<modint<md>> fact, inv, inv_fact;
void cominit(int MAX) {
    fact.resize(MAX + 1);
    inv.resize(MAX + 1);
    inv_fact.resize(MAX + 1);
    fact[0] = fact[1] = 1;
    inv_fact[0] = inv_fact[1] = 1;
    inv[1] = 1;
    for (int i = 2; i <= MAX; i++) {
        fact[i] = fact[i - 1] * i;
        inv[i] = -inv[md % i] * (modint<md>) (md / i);
        inv_fact[i] = inv_fact[i - 1] * inv[i];
    }
}
template <typename T>
modint<md> Com(T n, T k) {
    assert(n < (int) fact.size() && k < (int) fact.size());
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}
template <typename T>
modint<md> Per(T n, T k) {
    assert(n < (int) fact.size() && k < (int) fact.size());
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fact[n] * inv_fact[n - k];
}
using Mint = modint<md>;

template <int MOD>
vector<modint<MOD>> ntt(vector<modint<MOD>> A, modint<MOD> p_root) {
    int N = A.size();
    vector<int> bit(N);
    bit[0] = 0;
    int b = __builtin_ctz(N); // N = 1 << b
    for (int i = 0; i < b; i++) {
        int x = 1 << i, y = 1 << (b - 1 - i);
        for (int j = 0; j < (1 << i); j++) {
            bit[x + j] = bit[j] + y;
        }
    }
    vector<modint<MOD>> B(N);
    for (int i = 0; i < N; i++) {
        B[i] = A[bit[i]];
    }
    for (int i = 1; i <= b; i++) {
        modint<MOD> g = p_root.pow((modint<MOD>::mod() - 1) >> i);
        for (int j = 0; j < N; j += (1 << i)) {
            modint<MOD> om = 1;
            for (int k = 0; k < (1 << (i - 1)); k++) {
                modint<MOD> x = B[j + k], y = B[j + k + (1 << (i - 1))] * om;
                B[j + k] = x + y;
                B[j + k + (1 << (i - 1))] = x - y;
                om *= g;
            }
        }
    }
    return B;
}

/* vector<Mint> convolution998244353(vector<Mint> A, vector<Mint> B) {
    int N = (int) A.size(), M = (int) B.size();
    int deg = 1;
    while (deg < N + M) {
        deg <<= 1;
    }
    Mint p_root = 3;
    A.resize(deg), B.resize(deg);
    A = ntt(A, p_root);
    B = ntt(B, p_root);
    for (int i = 0; i < deg; i++) {
        A[i] *= B[i];
    }
    A = ntt(A, p_root.inv());
    A.resize(N + M - 1);
    Mint deg_inv = Mint(deg).inv();
    for (int i = 0; i < N + M - 1; i++) {
        A[i] *= deg_inv;
    }
    return A;
} */

using u64 = unsigned long long;

template <int MOD>
vector<modint<MOD>> convolution(vector<modint<MOD>> A, vector<modint<MOD>> B) {
    int N = (int) A.size(), M = (int) B.size();
    int deg = 1;
    while (deg < N + M) {
        deg <<= 1;
    }
    A.resize(deg), B.resize(deg);
    long long p_root = primitive_root(MOD);
    A = ntt(A, modint<MOD>(p_root));
    B = ntt(B, modint<MOD>(p_root));
    for (int i = 0; i < deg; i++) {
        A[i] *= B[i];
    }
    A = ntt(A, modint<MOD>(p_root).inv());
    A.resize(N + M - 1);
    modint<MOD> deg_inv = modint<MOD>(deg).inv();
    for (int i = 0; i < N + M - 1; i++) {
        A[i] *= deg_inv;
    }
    return A;
}

vector<long long> convolution_arbitrary_mod(vector<long long> &A, vector<long long> &B, u64 MOD) {
    static constexpr u64 MOD1 = 754974721;  // 2^24
    static constexpr u64 MOD2 = 167772161;  // 2^25
    static constexpr u64 MOD3 = 469762049;  // 2^26
    int N = A.size(), M = B.size();
    vector<modint<MOD1>> MA1(N), MB1(M);
    vector<modint<MOD2>> MA2(N), MB2(M);
    vector<modint<MOD3>> MA3(N), MB3(M);
    for (int i = 0; i < N; i++) {
        MA1[i] = A[i];
        MA2[i] = A[i];
        MA3[i] = A[i];
    }
    for (int i = 0; i < M; i++) {
        MB1[i] = B[i];
        MB2[i] = B[i];
        MB3[i] = B[i];
    }
    vector<modint<MOD1>> MC1 = convolution(MA1, MB1);
    vector<modint<MOD2>> MC2 = convolution(MA2, MB2);
    vector<modint<MOD3>> MC3 = convolution(MA3, MB3);
    vector<long long> C(N + M - 1);
    for (int i = 0; i < N + M - 1; i++) {
        vector<long long> R = {MC1[i].val(), MC2[i].val(), MC3[i].val()};
        vector<long long> M = {MOD1, MOD2, MOD3};
        C[i] = Garner(R, M, MOD);
    }
    return C;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<long long> A(N + 1);
    for (int i = 0; i < N + 1; i++) {
        cin >> A[i];
    }
    int M;
    cin >> M;
    vector<long long> B(M + 1);
    for (int i = 0; i < M + 1; i++) {
        cin >> B[i];
    }
    if (N == 0 && A[0] == 0) {
        cout << 0 << '\n';
        cout << 0 << '\n';
        return 0;
    }
    if (M == 0 && B[0] == 0) {
        cout << 0 << '\n';
        cout << 0 << '\n';
        return 0;
    }
    vector<long long> C = convolution_arbitrary_mod(A, B, 258280327);
    cout << N + M << '\n';
    for (int i = 0; i < N + M + 1; i++) {
        cout << C[i] << " \n"[i == N + M];
    }
}

yukicoder

結果

テストケース

ソースコード