結果

問題 No.2592 おでぶなおばけさん 2
ユーザー suisen
提出日時 2023-12-20 01:18:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 45 ms / 2,500 ms
コード長 1,084 bytes
コンパイル時間 1,419 ms
コンパイル使用メモリ 79,860 KB
最終ジャッジ日時 2025-02-18 12:27:59
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 83
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <vector>

#include <atcoder/modint>

using mint1 = atcoder::static_modint<818937857>;
using mint2 = atcoder::static_modint<850395137>;
using mint3 = atcoder::static_modint<907018241>;

template <typename R, typename T>
std::vector<R> poly_acc(const std::vector<T>& a, R x) {
    const int n = a.size();
    std::vector<R> sum(n + 1);
    R px = 1;
    for (int i = 0; i < n; ++i) {
        sum[i + 1] = sum[i] + R(a[i]) * px;
        px *= x;
    }
    return sum;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, q;
    long long k;

    std::cin >> n >> q >> k;

    std::vector<long long> a(n);
    for (auto &e : a) std::cin >> e;

    std::vector s1 = poly_acc<mint1>(a, k);
    std::vector s2 = poly_acc<mint2>(a, k);
    std::vector s3 = poly_acc<mint3>(a, k);

    while (q--) {
        int l, r;
        std::cin >> l >> r;
        --l;
        bool ans =
            s1[l] != s1[r] or
            s2[l] != s2[r] or
            s3[l] != s3[r];
        std::cout << (ans ? "Yes" : "No") << '\n';
    }
}
0