結果

問題 No.2348 Power!! (Easy)
コンテスト
ユーザー tokusakurai
提出日時 2023-07-16 00:20:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,648 ms / 5,000 ms
コード長 7,440 bytes
コンパイル時間 2,381 ms
コンパイル使用メモリ 206,312 KB
最終ジャッジ日時 2025-02-15 15:10:38
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct io_setup {
    io_setup() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout << fixed << setprecision(15);
    }
} io_setup;

template <typename T>
void print(const vector<T> &v, T x = 0) {
    int n = v.size();
    for (int i = 0; i < n; i++) cout << v[i] + x << (i == n - 1 ? '\n' : ' ');
    if (v.empty()) cout << '\n';
}

constexpr int MOD = 998244353;

template <int mod>
struct Mod_Int {
    int x;

    Mod_Int() : x(0) {}

    Mod_Int(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    static int get_mod() { return mod; }

    Mod_Int &operator+=(const Mod_Int &p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int &operator-=(const Mod_Int &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    Mod_Int &operator*=(const Mod_Int &p) {
        x = (int)(1LL * x * p.x % mod);
        return *this;
    }

    Mod_Int &operator/=(const Mod_Int &p) {
        *this *= p.inverse();
        return *this;
    }

    Mod_Int &operator++() { return *this += Mod_Int(1); }

    Mod_Int operator++(int) {
        Mod_Int tmp = *this;
        ++*this;
        return tmp;
    }

    Mod_Int &operator--() { return *this -= Mod_Int(1); }

    Mod_Int operator--(int) {
        Mod_Int tmp = *this;
        --*this;
        return tmp;
    }

    Mod_Int operator-() const { return Mod_Int(-x); }

    Mod_Int operator+(const Mod_Int &p) const { return Mod_Int(*this) += p; }

    Mod_Int operator-(const Mod_Int &p) const { return Mod_Int(*this) -= p; }

    Mod_Int operator*(const Mod_Int &p) const { return Mod_Int(*this) *= p; }

    Mod_Int operator/(const Mod_Int &p) const { return Mod_Int(*this) /= p; }

    bool operator==(const Mod_Int &p) const { return x == p.x; }

    bool operator!=(const Mod_Int &p) const { return x != p.x; }

    Mod_Int inverse() const {
        assert(*this != Mod_Int(0));
        return pow(mod - 2);
    }

    Mod_Int pow(long long k) const {
        Mod_Int now = *this, ret = 1;
        for (; k > 0; k >>= 1, now *= now) {
            if (k & 1) ret *= now;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const Mod_Int &p) { return os << p.x; }

    friend istream &operator>>(istream &is, Mod_Int &p) {
        long long a;
        is >> a;
        p = Mod_Int<mod>(a);
        return is;
    }
};

using mint = Mod_Int<MOD>;

template <typename T>
struct Number_Theoretic_Transform {
    static int max_base;
    static T root;
    static vector<T> r, ir;

    Number_Theoretic_Transform() {}

    static void init() {
        if (!r.empty()) return;
        int mod = T::get_mod();
        int tmp = mod - 1;
        root = 2;
        while (root.pow(tmp >> 1) == 1) root++;
        max_base = 0;
        while (tmp % 2 == 0) tmp >>= 1, max_base++;
        r.resize(max_base), ir.resize(max_base);
        for (int i = 0; i < max_base; i++) {
            r[i] = -root.pow((mod - 1) >> (i + 2)); // r[i]  := 1 の 2^(i+2) 乗根
            ir[i] = r[i].inverse();                 // ir[i] := 1/r[i]
        }
    }

    static void ntt(vector<T> &a) {
        init();
        int n = a.size();
        assert((n & (n - 1)) == 0);
        assert(n <= (1 << max_base));
        for (int k = n; k >>= 1;) {
            T w = 1;
            for (int s = 0, t = 0; s < n; s += 2 * k) {
                for (int i = s, j = s + k; i < s + k; i++, j++) {
                    T x = a[i], y = w * a[j];
                    a[i] = x + y, a[j] = x - y;
                }
                w *= r[__builtin_ctz(++t)];
            }
        }
    }

    static void intt(vector<T> &a) {
        init();
        int n = a.size();
        assert((n & (n - 1)) == 0);
        assert(n <= (1 << max_base));
        for (int k = 1; k < n; k <<= 1) {
            T w = 1;
            for (int s = 0, t = 0; s < n; s += 2 * k) {
                for (int i = s, j = s + k; i < s + k; i++, j++) {
                    T x = a[i], y = a[j];
                    a[i] = x + y, a[j] = w * (x - y);
                }
                w *= ir[__builtin_ctz(++t)];
            }
        }
        T inv = T(n).inverse();
        for (auto &e : a) e *= inv;
    }

    static vector<T> convolve(vector<T> a, vector<T> b) {
        if (a.empty() || b.empty()) return {};
        if (min(a.size(), b.size()) < 40) {
            int n = a.size(), m = b.size();
            vector<T> c(n + m - 1, 0);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) c[i + j] += a[i] * b[j];
            }
            return c;
        }
        int k = (int)a.size() + (int)b.size() - 1, n = 1;
        while (n < k) n <<= 1;
        a.resize(n, 0), b.resize(n, 0);
        ntt(a), ntt(b);
        for (int i = 0; i < n; i++) a[i] *= b[i];
        intt(a), a.resize(k);
        return a;
    }
};

template <typename T>
int Number_Theoretic_Transform<T>::max_base = 0;

template <typename T>
T Number_Theoretic_Transform<T>::root = T();

template <typename T>
vector<T> Number_Theoretic_Transform<T>::r = vector<T>();

template <typename T>
vector<T> Number_Theoretic_Transform<T>::ir = vector<T>();

using NTT = Number_Theoretic_Transform<mint>;

template <typename T>
vector<T> multipoint_evaluation_geometric_series(vector<T> f, T a, T r, int m) {
    if (m == 0) return {};
    int n = f.size();
    T c = 1;
    for (int i = 0; i < n; i++) {
        f[i] *= c;
        c *= a;
    }
    if (r == T(0)) {
        vector<mint> ret(m, 0);
        for (int i = 0; i < n; i++) ret[0] += f[i];
        for (int j = 1; j < m; j++) ret[j] = f[0];
        return ret;
    }
    int s = 1;
    while (s < n + m - 1) s <<= 1;
    T ir = r.inverse();
    vector<T> pw(n + m - 1, 1);
    for (int i = 1; i < n + m - 1; i++) pw[i] = pw[i - 1] * r;
    for (int i = 1; i < n + m - 1; i++) pw[i] *= pw[i - 1];
    vector<T> ipw(max(n, m), 1);
    for (int i = 1; i < max(n, m); i++) ipw[i] = ipw[i - 1] * ir;
    for (int i = 1; i < max(n, m); i++) ipw[i] *= ipw[i - 1];
    vector<T> g1(s, 0), g2(s, 0);
    for (int i = 0; i < n; i++) g1[n - 1 - i] = f[i] * ipw[i];
    for (int k = 0; k < n + m - 1; k++) g2[k] = pw[k];
    NTT::ntt(g1), NTT::ntt(g2);
    for (int i = 0; i < s; i++) g1[i] *= g2[i];
    NTT::intt(g1);
    vector<T> ret(m, 0);
    for (int j = 0; j < m; j++) ret[j] = g1[n - 1 + j] * ipw[j];
    return ret;
}

template <typename T>
T kth_root_integer(T a, int k) {
    if (k == 1) return a;
    auto check = [&](T x) {
        T mul = 1;
        for (int j = 0; j < k; j++) {
            if (__builtin_mul_overflow(mul, x, &mul)) return false;
        }
        return mul <= a;
    };
    int n = 4 * sizeof(T);
    T ret = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (check(ret | (T(1) << i))) ret |= T(1) << i;
    }
    return ret;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        mint A;
        int N;
        cin >> A >> N;

        int D = kth_root_integer(N, 2);
        vector<mint> f(D, 0);
        for (int i = 0; i < D; i++) f[i] = A.pow(i * i);

        mint r = A.pow(2 * D);
        auto g = multipoint_evaluation_geometric_series(f, mint(1), r, D);

        mint ans = 0;
        for (int k = 0; k < D; k++) ans += A.pow(1LL * D * D * k * k) * g[k];
        for (int i = D * D; i < N; i++) ans += A.pow(1LL * i * i);

        cout << ans << '\n';
    }
}
0