結果

問題 No.2592 おでぶなおばけさん 2
ユーザー 👑 nu50218nu50218
提出日時 2023-12-05 16:55:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 294 ms / 2,500 ms
コード長 1,946 bytes
コンパイル時間 2,268 ms
コンパイル使用メモリ 206,520 KB
実行使用メモリ 6,912 KB
最終ジャッジ日時 2023-12-20 11:13:17
合計ジャッジ時間 27,453 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 33 ms
6,676 KB
testcase_02 AC 100 ms
6,676 KB
testcase_03 AC 43 ms
6,676 KB
testcase_04 AC 61 ms
6,676 KB
testcase_05 AC 99 ms
6,912 KB
testcase_06 AC 101 ms
6,676 KB
testcase_07 AC 146 ms
6,676 KB
testcase_08 AC 100 ms
6,676 KB
testcase_09 AC 39 ms
6,676 KB
testcase_10 AC 94 ms
6,676 KB
testcase_11 AC 98 ms
6,676 KB
testcase_12 AC 26 ms
6,676 KB
testcase_13 AC 245 ms
6,676 KB
testcase_14 AC 247 ms
6,676 KB
testcase_15 AC 232 ms
6,676 KB
testcase_16 AC 249 ms
6,676 KB
testcase_17 AC 257 ms
6,676 KB
testcase_18 AC 233 ms
6,676 KB
testcase_19 AC 221 ms
6,676 KB
testcase_20 AC 208 ms
6,676 KB
testcase_21 AC 202 ms
6,676 KB
testcase_22 AC 215 ms
6,676 KB
testcase_23 AC 260 ms
6,676 KB
testcase_24 AC 239 ms
6,676 KB
testcase_25 AC 211 ms
6,676 KB
testcase_26 AC 211 ms
6,676 KB
testcase_27 AC 294 ms
6,912 KB
testcase_28 AC 278 ms
6,912 KB
testcase_29 AC 283 ms
6,912 KB
testcase_30 AC 282 ms
6,912 KB
testcase_31 AC 281 ms
6,912 KB
testcase_32 AC 281 ms
6,912 KB
testcase_33 AC 283 ms
6,912 KB
testcase_34 AC 278 ms
6,912 KB
testcase_35 AC 278 ms
6,912 KB
testcase_36 AC 280 ms
6,912 KB
testcase_37 AC 279 ms
6,912 KB
testcase_38 AC 279 ms
6,912 KB
testcase_39 AC 278 ms
6,912 KB
testcase_40 AC 282 ms
6,912 KB
testcase_41 AC 280 ms
6,912 KB
testcase_42 AC 279 ms
6,912 KB
testcase_43 AC 281 ms
6,912 KB
testcase_44 AC 288 ms
6,912 KB
testcase_45 AC 278 ms
6,912 KB
testcase_46 AC 280 ms
6,912 KB
testcase_47 AC 250 ms
6,912 KB
testcase_48 AC 250 ms
6,912 KB
testcase_49 AC 250 ms
6,912 KB
testcase_50 AC 251 ms
6,912 KB
testcase_51 AC 250 ms
6,912 KB
testcase_52 AC 277 ms
6,912 KB
testcase_53 AC 277 ms
6,912 KB
testcase_54 AC 276 ms
6,912 KB
testcase_55 AC 277 ms
6,912 KB
testcase_56 AC 279 ms
6,912 KB
testcase_57 AC 51 ms
6,912 KB
testcase_58 AC 279 ms
6,912 KB
testcase_59 AC 280 ms
6,912 KB
testcase_60 AC 282 ms
6,912 KB
testcase_61 AC 281 ms
6,912 KB
testcase_62 AC 280 ms
6,912 KB
testcase_63 AC 277 ms
6,912 KB
testcase_64 AC 281 ms
6,912 KB
testcase_65 AC 271 ms
6,912 KB
testcase_66 AC 271 ms
6,912 KB
testcase_67 AC 268 ms
6,912 KB
testcase_68 AC 273 ms
6,912 KB
testcase_69 AC 270 ms
6,912 KB
testcase_70 AC 272 ms
6,912 KB
testcase_71 AC 271 ms
6,912 KB
testcase_72 AC 271 ms
6,912 KB
testcase_73 AC 274 ms
6,912 KB
testcase_74 AC 2 ms
6,676 KB
testcase_75 AC 280 ms
6,912 KB
testcase_76 AC 278 ms
6,912 KB
testcase_77 AC 277 ms
6,912 KB
testcase_78 AC 279 ms
6,912 KB
testcase_79 AC 283 ms
6,912 KB
testcase_80 AC 279 ms
6,912 KB
testcase_81 AC 279 ms
6,912 KB
testcase_82 AC 279 ms
6,912 KB
testcase_83 AC 277 ms
6,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/segtree.hpp>

using namespace std;
using ll = long long;

// [1e18, 5e18] からランダムな素数を取ってくる
// ミラーラビンとか使えば実行時にランダムに出来るのでハックありでも対応可能
// https://www.wolframalpha.com/input?i=RandomPrime%5B%7B10%5E18%2C+5*10%5E18%7D%5D
const ll MOD = 4554013204529924683;
static_assert(MOD < numeric_limits<ll>::max() / 2);

using S = ll;
S op(const S a, const S b) {
    return (a + b) % MOD;
}
S e() {
    return 0;
}
using segtree = atcoder::segtree<S, op, e>;

int main() {
    ll n, q, k;
    cin >> n >> q >> k;

    vector<ll> a(n);
    for (auto& x : a) {
        cin >> x;

        // 今後 % MOD の値しか使わないので、正の数にしておく
        x = (x + MOD) % MOD;
    }

    // b[i] := (a[i] * pow(k, i)) % MOD
    vector<ll> b(n);
    __uint128_t powk = 1;
    for (int i = 0; i < n; i++) {
        // a[i], powk ともに MOD < 2^63 以下なので、128ビットで十分
        b[i] = (a[i] * powk) % MOD;
        powk *= k;
        powk %= MOD;
    }

    segtree st(b);

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;

        // S = Σ_{i=l}^r (a_i k^{i-l}) として、
        // S = 0 かどうかを、S % MOD = 0 かどうかで判定する。
        // この方法で高い確率で正解できる。
        //
        // 判定が誤るのは S ≡ 0 かつ S > 0 のとき、すなわち S が MOD を素因数として含むとき。
        // しかしながら MOD として取りうる値は 10^16個ぐらいあり、
        // （ https://ja.wikipedia.org/wiki/素数定理 の π(10^18) あたりを参照）
        // S は高々 r-l <= 10^5 個程度しか 10^18 以上の素因数を含まないので、その確率は非常に低い。
        cout << (st.prod(l, r + 1) ? "Yes" : "No") << endl;
    }
}
0